• 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

Probabilistic graph-coloring in bipartite and split graphs

Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009), Probabilistic graph-coloring in bipartite and split graphs, Journal of Combinatorial Optimization, 17, 3, p. 274-311. http://dx.doi.org/10.1007/s10878-007-9112-2

View/Open
cahierLamsade268.pdf (541.7Kb)
Type
Article accepté pour publication ou publié
Date
2009
Journal name
Journal of Combinatorial Optimization
Volume
17
Number
3
Publisher
Springer Netherlands
Pages
274-311
Publication identifier
http://dx.doi.org/10.1007/s10878-007-9112-2
Metadata
Show full item record
Author(s)
Murat, Cécile
Escoffier, Bruno
Della Croce, Federico
Bourgeois, Nicolas
Paschos, Vangelis
Abstract (EN)
We revisit in this paper the stochastic model for minimum graph-coloring introduced in (Murat and Paschos in Discrete Appl. Math. 154:564–586, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standard-approximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standard-approximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P=NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs.
Subjects / Keywords
Probabilistic optimization; Approximation algorithms; Graph coloring

Related items

Showing items related by title and author.

  • Thumbnail
    Probabilistic coloring of bipartite and split graphs 
    Della Croce, Federico; Escoffier, Bruno; Murat, Cécile; Paschos, Vangelis (2005) Communication / Conférence
  • 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
    Algorithms for dominating clique problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
  • Thumbnail
    Fast algorithms for min independent dominating set 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013) Communication / Conférence
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