Skip to Main Content (Press Enter)

Logo UNICH
  • ×
  • Home
  • Corsi
  • Insegnamenti
  • Professioni
  • Persone
  • Pubblicazioni
  • Strutture
  • Terza Missione
  • Attività
  • Competenze

UNI-FIND
Logo UNICH

|

UNI-FIND

unich.it
  • ×
  • Home
  • Corsi
  • Insegnamenti
  • Professioni
  • Persone
  • Pubblicazioni
  • Strutture
  • Terza Missione
  • Attività
  • Competenze
  1. Pubblicazioni

Independent domination versus weighted independent domination

Articolo
Data di Pubblicazione:
2020
Abstract:
INDEPENDENT DOMINATION is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NP-hardness of the weighted version in a certain class to the unweighted case. Second, we strengthen polynomial-time solvability of the unweighted version in the class of P2+P3-free graphs to the weighted case. This result is tight in the sense that both versions are NP-hard in the class of P3+P3-free graphs, i.e. P3+P3 is a minimal graph forbidding of which produces an NP-hard case for both versions of the problem.
Tipologia CRIS:
1.1 Articolo in rivista
Keywords:
Algorithms; Independent domination; NP-hardness; Polynomial-time; Weighted independent domination
Elenco autori:
Lozin, V.; Malyshev, D.; Mosca, R.; Zamaraev, V.
Autori di Ateneo:
MOSCA Raffaele
Link alla scheda completa:
https://ricerca.unich.it/handle/11564/717083
Pubblicato in:
INFORMATION PROCESSING LETTERS
Journal
  • Dati Generali

Dati Generali

URL

https://www.sciencedirect.com/science/article/pii/S0020019020300016
  • Utilizzo dei cookie

Realizzato con VIVO | Designed by Cineca | 26.5.0.0