The complexity of minimum convex coloring

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

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

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

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)

Cites Work

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

Cited In (18)

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

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)