The complexity of minimum convex coloring

DOI10.1016/J.DAM.2011.09.022zbMATH Open1238.05091OpenAlexW1983029152MaRDI QIDQ415283FDOQ415283

Authors Frank Kammer, Torsten Tholey

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.09.022

zbMATH Keywords

approximation algorithmtreewidthconvex coloringset covermaximum disjoint paths problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

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

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• Approximation and Online Algorithms
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Efficient approximation of convex recolorings
• Graph minors. I. Excluding a forest
• Graph minors. XIII: The disjoint paths problem
• Hardness of the undirected edge-disjoint paths problem
• Inapproximability and approximability of maximal tree routing and coloring
• On the Computational Complexity of Combinatorial Problems
• Partial convex recolorings of trees and galled networks
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• The Complexity of Minimum Convex Coloring

Cited in

(18)

• Strong intractability results for generalized convex recoloring problems
• Strong intractability of generalized convex recoloring problems
• Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)
• scientific article; zbMATH DE number 1839437 (Why is no real title available?)
• Approximation of min coloring by moderately exponential algorithms
• The Complexity of Minimum Convex Coloring
• Hardness and inapproximability of convex recoloring problems
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• A GRASP for the convex recoloring problem in graphs
• A short proof of the NP-completeness of minimum sum interval coloring
• An extended formulation of the convex recoloring problem on a tree
• The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
• Between Colorings and Layouts - Minimum Morphism Cost Problems
• 1.5-approximation algorithm for the 2-convex recoloring problem
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• The convex recoloring problem: polyhedra, facets and computational experiments
• On the minimum load coloring problem
• On the approximation of Min Split-coloring and Min Cocoloring

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 Q415283)