On Computational Aspects of Greedy Partitioning of Graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

On Computational Aspects of Greedy Partitioning of Graphs

Abstrakt

In this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite number of classes P. On the other hand we get a polynomial-time certifying algorithm if k is fixed and the family of minimal forbidden graphs defining the class P is finite. We also prove coNP-completeness of the problem of deciding whether for a given graph G 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 a given constant. A new Brooks-type bound on the largest number of colors used by the greedy P-coloring algorithm is given.

Cytowania

1
CrossRef
1
Web of Science
1
Scopus

Piotr Borowiecki. (2017). On Computational Aspects of Greedy Partitioning of Graphs, 10336, 34-46. https://doi.org/10.1007/978-3-319-59605-1_4

Informacje szczegółowe

Kategoria:
Inna publikacyjna praca zbiorowa (w tym materiały konferencyjne)
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Frontiers in Algorithmics strony 34 - 46
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
Borowiecki P.: On Computational Aspects of Greedy Partitioning of Graphs// Frontiers in Algorithmics/ : , 2017, s.34-46

wyświetlono 28 razy

Publikacje, które mogą cię zainteresować

Meta Tagi