Computational aspects of greedy partitioning of graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Computational aspects of greedy partitioning of graphs

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

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 220 razy

Publikacje, które mogą cię zainteresować

Meta Tagi