Computational aspects of greedy partitioning of graphs - Publication - Bridge of Knowledge

Search

Computational aspects of greedy partitioning of graphs

Abstract

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.

Citations

  • 2

    CrossRef

  • 0

    Web of Science

  • 5

    Scopus

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
JOURNAL OF COMBINATORIAL OPTIMIZATION no. 35, pages 641 - 665,
ISSN: 1382-6905
Language:
English
Publication year:
2018
Bibliographic description:
Borowiecki P.: Computational aspects of greedy partitioning of graphs// JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 35, nr. 2 (2018), s.641-665
DOI:
Digital Object Identifier (open in new tab) 10.1007/s10878-017-0185-2
Verified by:
Gdańsk University of Technology

seen 210 times

Recommended for you

Meta Tags