Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s10878-007-9112-2 | J. Comb. Optim. |
Keywords | DocType | Volume |
Probabilistic optimization,Approximation algorithms,Graph coloring | Journal | 17 |
Issue | ISSN | Citations |
3 | 1382-6905 | 3 |
PageRank | References | Authors |
0.37 | 15 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Bourgeois | 1 | 99 | 7.96 |
| Federico Della Croce | 2 | 399 | 41.60 |
| Bruno Escoffier | 3 | 430 | 37.32 |
| Cécile Murat | 4 | 246 | 12.61 |
| Vangelis Th. Paschos | 5 | 633 | 63.97 |