The Complexity of Minimum Convex Coloring

DOI10.1007/978-3-540-92182-0_5MaRDI QIDQ3596703zbMATH OpenOpenAlexFDO

Authors Frank Kammer, Torsten Tholey

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_5

zbMATH Keywords

convex coloringmaximum disjoint paths problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)

Recommendations

• The complexity of minimum convex coloring
• Hardness and inapproximability of convex recoloring problems
• On the complexity of solving or approximating convex recoloring problems
• 1.5-approximation algorithm for the 2-convex recoloring problem
• 1.5-approximation algorithm for the 2-convex recoloring problem

Cited in

(12)

• Convex recoloring of paths
• On the minimum load coloring problem
• A short proof of the NP-completeness of minimum sum interval coloring
• Convex recoloring of paths
• Between Colorings and Layouts - Minimum Morphism Cost Problems
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• The complexity of minimum convex coloring
• Removing local extrema from imprecise terrains
• scientific article; zbMATH DE number 1839437 (Why is no real title available?)
• On the approximation of Min Split-coloring and Min Cocoloring
• Quadratic kernelization for convex recoloring of trees
• Approximation of min coloring by moderately exponential algorithms

This page was built for publication: The Complexity of Minimum Convex Coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3596703)