Approximation of min coloring by moderately exponential algorithms

DOI10.1016/j.ipl.2009.05.002zbMath1197.05141MaRDI QIDQ989534

Vangelis Th. Paschos, Nicolas Bourgeois, Bruno Escoffier

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2649

zbMATH Keywords

approximation algorithms; exponential algorithms; min coloring problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

An exponential time 2-approximation algorithm for bandwidth, Algorithms for dominating clique problems, Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Enumerating maximal independent sets with applications to graph colouring.
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• A still better performance guarantee for approximate graph coloring
• Approximation algorithms for combinatorial problems
• Improved approximations for weighted and unweighted graph problems
• z-Approximations
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Measure and conquer