Algorithmic and hardness results for the colorful components problems

DOI10.1007/s00453-014-9926-0zbMath1330.68087arXiv1311.1298WikidataQ58203664 ScholiaQ58203664MaRDI QIDQ747623

Alexandru Popa, Anna Adamaszek

Publication date: 19 October 2015

Published in: Algorithmica, LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.1298

zbMATH Keywords

graph coloring; hardness of approximation; colorful components; exact polynomial-time algorithms

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

92D10: Genetics and epigenetics

05C40: Connectivity