Wyszukiwarka
Abstrakt
In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs P-coloring with at least k colors is NP-complete if P is a class of Kp-free graphs with p>=3. On the other hand we give a polynomial-time algorithm when k is fixed and the family of minimal forbidden graphs defining the class P is finite. We also prove coNP-completeness of deciding if for a given graph G and an integer t>=0 the difference between the largest number of colors used by the greedy algorithm and the minimum number of colors required in any P-coloring of G is bounded by t. In view of computational hardness, we present new Brooks-type bound on the largest number of colors used by the greedy P-coloring algorithm.
Cytowania
-
2
CrossRef
-
0
Web of Science
-
5
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-017-0185-2
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
nr 35,
strony 641 - 665,
ISSN: 1382-6905 - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Borowiecki P.: Computational aspects of greedy partitioning of graphs// JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 35, nr. 2 (2018), s.641-665
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-017-0185-2
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 219 razy