Approximation of min coloring by moderately exponential algorithms

DOI10.1016/J.IPL.2009.05.002zbMath1197.05141OpenAlexW2159978956MaRDI QIDQ989534

Bruno Escoffier, Vangelis Th. Paschos, Nicolas Bourgeois

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 algorithmsexponential algorithmsmin coloring problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

Time-approximation trade-offs for inapproximable problems ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Exponential approximation schemata for some network design problems ⋮ Super-polynomial approximation branching algorithms ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ In)approximability of Maximum Minimal FVS ⋮ Algorithms for dominating clique problems ⋮ (In)approximability of maximum minimal FVS ⋮ On subexponential and FPT-time inapproximability ⋮ 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

This page was built for publication: Approximation of min coloring by moderately exponential algorithms