Algorithmic and hardness results for the colorful components problems

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

Anna Adamaszek, Alexandru Popa

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 coloringhardness of approximationcolorful componentsexact polynomial-time algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10) Connectivity (05C40)

Related Items (4)

Parameterized complexity and approximation issues for the colorful components problems ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem ⋮ Finding a Small Number of Colourful Components

Cites Work

• Unnamed Item
• The multi-multiway cut problem
• Non deterministic polynomial optimization problems and their approximations
• Zero knowledge and the chromatic number
• Partitioning into Colorful Components by Minimum Edge Deletions
• OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Approximation Algorithms for Some Graph Partitioning Problems

This page was built for publication: Algorithmic and hardness results for the colorful components problems