• 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 coloring of bipartite and split graphs

Della Croce, Federico; Escoffier, Bruno; Murat, Cécile; Paschos, Vangelis (2005), Probabilistic coloring of bipartite and split graphs, in Gervasi, Osvaldo; Gavrilova, Marina; Kumar, Vipin; Lagana, Antonio; Lee, Heow Pueh; Mun, Youngsong; Taniar, David; Tan, Chih Jeng Kenneth, Computational Science and Its Applications - ICCSA 2005 International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV, Springer : Berlin, p. 91-97. http://dx.doi.org/10.1007/11424925_23

View/Open
cahier218.pdf (434.5Kb)
Type
Communication / Conférence
Date
2005
Conference title
International Conference on Computational Science and Its Applications (ICCSA'05)
Conference date
2005-05
Conference city
Singapour
Conference country
Singapour
Book title
Computational Science and Its Applications - ICCSA 2005 International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV
Book author
Gervasi, Osvaldo; Gavrilova, Marina; Kumar, Vipin; Lagana, Antonio; Lee, Heow Pueh; Mun, Youngsong; Taniar, David; Tan, Chih Jeng Kenneth
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3483
Published in
Berlin
ISBN
978-3-540-25863-6
Number of pages
1362
Pages
91-97
Publication identifier
http://dx.doi.org/10.1007/11424925_23
Metadata
Show full item record
Author(s)
Della Croce, Federico
Escoffier, Bruno
Murat, Cécile
Paschos, Vangelis
Abstract (EN)
We revisit in this paper the probabilistic coloring problem (probabilistic coloring) and focus ourselves on bipartite and split graphs. We first give some general properties dealing with the optimal solution. We then show that the unique 2-coloring achieves approximation ratio 2 in bipartite graphs under any system of vertex-probabilities and propose a polynomial algorithm achieving tight approximation ratio 8/7 under identical vertex-probabilities. Then we deal with restricted cases of bipartite graphs. Main results for these cases are the following. Under non-identical vertex-probabilities probabilistic coloring is polynomial for stars, for trees with bounded degree and a fixed number of distinct vertex-probabilities, and, consequently, also for paths with a fixed number of distinct vertex-probabilities. Under identical vertex-probabilities, probabilistic coloring is polynomial for paths, for even and odd cycles and for trees whose leaves are either at even or at odd levels. Next, we deal with split graphs and show that probabilistic coloring is NP-hard, even under identical vertex-probabilities. Finally, we study approximation in split graphs and provide a 2-approximation algorithm for the case of distinct probabilities and a polynomial time approximation schema under identical vertex-probabilities.
Subjects / Keywords
Polynomial algorithm; coloring problem; Approximation algorithms

Related items

Showing items related by title and author.

  • 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é
  • 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
    On the probabilistic minimum coloring and minimum k-coloring 
    Murat, Cécile; Paschos, Vangelis (2006) Article accepté pour publication ou publié
  • Thumbnail
    Worst-case complexity of exact algorithms for NP-hard problems 
    Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
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