The complexity of minimum convex coloring

DOI10.1016/j.dam.2011.09.022zbMath1238.05091OpenAlexW1983029152MaRDI QIDQ415283

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 algorithmtreewidthset coverconvex coloringmaximum disjoint paths problem

Mathematics Subject Classification ID

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

Related Items (10)

Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ A GRASP for the convex recoloring problem in graphs ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability of generalized convex recoloring problems ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Strong inequalities and a branch-and-price algorithm for the convex recoloring problem ⋮ Hardness and inapproximability of convex recoloring problems ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

Cites Work

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

This page was built for publication: The complexity of minimum convex coloring