Approximation of min coloring by moderately exponential algorithms
DOI10.1016/J.IPL.2009.05.002zbMATH Open1197.05141OpenAlexW2159978956MaRDI QIDQ989534FDOQ989534
Authors: Bruno Escoffier, Nicolas Bourgeois, Vangelis Th. Paschos 
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
Recommendations
- Approximation results for the minimum graph coloring problem
- On the approximation of Min Split-coloring and Min Cocoloring
- Automata, Languages and Programming
- Polynomial-time approximation algorithms for the coloring problem in some cases
- The complexity of minimum convex coloring
- The Complexity of Minimum Convex Coloring
- scientific article; zbMATH DE number 1839437
- scientific article; zbMATH DE number 7650095
- Exact and approximative algorithms for coloring G(n,p)
- An approximate algorithm for the \( (k,d)\)-coloring problem
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- \(z\)-approximations
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Enumerating maximal independent sets with applications to graph colouring.
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Measure and conquer
- A still better performance guarantee for approximate graph coloring
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Improved approximations for weighted and unweighted graph problems
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (14)
- An exponential time 2-approximation algorithm for bandwidth
- Exponential approximation schemata for some network design problems
- Title not available (Why is that?)
- Algorithms for dominating clique problems
- In)approximability of Maximum Minimal FVS
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Super-polynomial approximation branching algorithms
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- (In)approximability of maximum minimal FVS
- Time-approximation trade-offs for inapproximable problems
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- On the approximation of Min Split-coloring and Min Cocoloring
- On the greatest number of 2 and 3 colorings of a (v, e)-graph
- Moderately exponential time and fixed parameter approximation algorithms
This page was built for publication: Approximation of min coloring by moderately exponential algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989534)
