• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Polynomial approximation and graph-coloring

Paschos, Vangelis (2003), Polynomial approximation and graph-coloring, Computing, 70, 1, p. 41-86. http://dx.doi.org/10.1007/s00607-002-1468-7

View/Open
publi142.pdf (541.7Kb)
Type
Article accepté pour publication ou publié
Date
2003
Journal name
Computing
Volume
70
Number
1
Publisher
Springer Wien
Pages
41-86
Publication identifier
http://dx.doi.org/10.1007/s00607-002-1468-7
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Abstract (EN)
Consider a graph G=(V,E) of order n. In the minimum graph-coloring problem we try to color V with as few colors as possible so that no two adjacent vertices receive the same color. This problem is among the first ones proved to be intractable, and hence, it is very unlikely that an optimal polynomial-time algorithm could ever be devised for it. In this paper, we survey the main polynomial time approximation algorithms (the ones for which theoretical approximability bounds have been studied) for the minimum graph-coloring and we discuss their approximation performance and their complexity. Finally, we further improve the approximation ratio for graph-coloring.
Subjects / Keywords
Graph; Coloring; Complexity; NP-complete; Approximation algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    Weighted coloring on planar, bipartite and split graphs: complexity and approximation 
    Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
  • Thumbnail
    Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation 
    de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
  • Thumbnail
    Approximation results for the minimum graph coloring problem 
    Paschos, Vangelis; Grisoni, Pascal; Demange, Marc (1994) Article accepté pour publication ou publié
  • Thumbnail
    A note on the approximation ratio of graph-coloring 
    Paschos, Vangelis (2001) Article accepté pour publication ou publié
  • Thumbnail
    Probabilistic graph-coloring in bipartite and split graphs 
    Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo