
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
Type
Communication / ConférenceDate
2005Conference title
International Conference on Computational Science and Its Applications (ICCSA'05)Conference date
2005-05Conference city
SingapourConference country
SingapourBook title
Computational Science and Its Applications - ICCSA 2005 International Conference, Singapore, May 9-12, 2005, Proceedings, Part IVBook author
Gervasi, Osvaldo; Gavrilova, Marina; Kumar, Vipin; Lagana, Antonio; Lee, Heow Pueh; Mun, Youngsong; Taniar, David; Tan, Chih Jeng KennethPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
3483Published in
Berlin
ISBN
978-3-540-25863-6
Number of pages
1362Pages
91-97
Publication identifier
Metadata
Show full item recordAbstract (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 algorithmsRelated items
Showing items related by title and author.
-
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
-
de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
-
Murat, Cécile; Paschos, Vangelis (2006) Article accepté pour publication ou publié
-
Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage