Data di Pubblicazione:
2021
Citazione:
Monopolar graphs: Complexity of computing classical graph parameters / M. Barbato, D. Bezzi. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 291:(2021 Mar 11), pp. 277-285. [10.1016/j.dam.2020.12.023]
Abstract:
A graph G = (V, E) is monopolar if V can be partitioned into a stable set and a set inducing the union of vertex-disjoint cliques. Motivated by an application of the clique partitioning problem on monopolar graphs to the cosmetic manufacturing, we study the complexity of computing classical graph parameters on the class of monopolar graphs. We show that computing the clique partitioning, stability and chromatic numbers of monopolar graphs is NP-hard. Conversely, we prove that every monopolar graph has a polynomial number of maximal cliques thus obtaining that a maximum-weight clique can be found in polynomial time on monopolar graphs.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Computational complexity; Monopolar graph; Maximum-weight clique; Clique partitioning; Stable set; Graph coloring
Elenco autori:
M. Barbato, D. Bezzi
Link alla scheda completa:
Link al Full Text:
Progetto: