
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
Type
Article accepté pour publication ou publiéDate
2009Journal name
Journal of Combinatorial OptimizationVolume
17Number
3Publisher
Springer Netherlands
Pages
274-311
Publication identifier
Metadata
Show full item recordAbstract (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 coloringRelated items
Showing items related by title and author.
-
Della Croce, Federico; Escoffier, Bruno; Murat, Cécile; Paschos, Vangelis (2005) Communication / Conférence
-
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
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013) Communication / Conférence