Approximation of min coloring by moderately exponential algorithms
type: Item
instance of: scholarly article
title: Approximation of min coloring by moderately exponential algorithms
zbMATH Open document ID: 1197.05141
author: Bruno Escoffier
author: Nicolas Bourgeois
author: Vangelis Th. Paschos
published in: Information Processing Letters
publication date: 2010-08-20T00:00:00Z
full work available at URL: https://basepub.dauphine.fr/handle/123456789/2649
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5773831
zbMATH Keywords: min coloring problem
zbMATH Keywords: exponential algorithms
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
OpenAlex ID: W2159978956
cites work: Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
cites work: Q3941433
cites work: Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
cites work: Efficient approximation of Min Set Cover by moderately exponential algorithms
cites work: Enumerating maximal independent sets with applications to graph colouring.
cites work: Improved approximations for weighted and unweighted graph problems
cites work: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
cites work: Q4778579
cites work: Measure and conquer
cites work: A still better performance guarantee for approximate graph coloring
cites work: Q4938668
cites work: \(z\)-approximations
cites work: Approximation algorithms for combinatorial problems
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.IPL.2009.05.002
Recommended article: Approximation results for the minimum graph coloring problem
Recommended article: On the approximation of Min Split-coloring and Min Cocoloring
Recommended article: Automata, Languages and Programming
Recommended article: Polynomial-time approximation algorithms for the coloring problem in some cases
Recommended article: The complexity of minimum convex coloring
Recommended article: The Complexity of Minimum Convex Coloring
Recommended article: Q4782702
Recommended article: Q5875482
Recommended article: Exact and approximative algorithms for coloring G(n,p)
Recommended article: Q3572597
description: scientific article; zbMATH DE number 5773831