Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Murat, C., Paschos, V.T.: The probabilistic minimum coloring problem. Annales du LAMSADE 1, LAMSADE, Universit Paris-Dauphine (2003), Available on http://l1.lamsade.dauphine.fr/~paschos/documents/a1pc.pdf
Murat, C., Paschos, V.T.: The probabilistic minimum coloring problem. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 346–357. Springer, Heidelberg (2003)
Averbakh, I., Berman, O., Simchi-Levi, D.: Probabilistic a priori routing-location problems. Naval Res. Logistics 41, 973–989 (1994)
Bertsimas, D.J.: On probabilistic traveling salesman facility location problems. Transportation Sci. 3, 184–191 (1989)
Bertsimas, D.J.: The probabilistic minimum spanning tree problem. Networks 20, 245–275 (1990)
Bertsimas, D.J., Jaillet, P., Odoni, A.: A priori optimization. Oper. Res. 38, 1019–1033 (1990)
Jaillet, P.: Probabilistic traveling salesman problem. Technical Report 185, Operations Research Center, MIT, Cambridge Mass, USA (1985)
Jaillet, P.: A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36, 929–936 (1988)
Jaillet, P.: Shortest path problems with node failures. Networks 22, 589–605 (1992)
Jaillet, P., Odoni, A.: The probabilistic vehicle routing problem. In: Golden, B.L., Assad, A.A. (eds.) Vehicle routing: methods and studies. North Holland, Amsterdam (1988)
Murat, C., Paschos, V.T.: The probabilistic minimum vertex-covering problem. Int. Trans. Opl Res. 9, 19–32 (2002)
Murat, C., Paschos, V.T.: The probabilistic longest path problem. Networks 33, 207–219 (1999)
Murat, C., Paschos, V.T.: A priori optimization for the probabilistic maximum independent set problem. Theoret. Comput. Sci. 270, 561–590 (2002)
Della Croce, F., Escoffier, B., Murat, C., Paschos, V.T.: Probabilistic coloring of bipartite and split graphs. Cahier du LAMSADE 218, LAMSADE, Universit Paris-Dauphine (2004)
Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Della Croce, F., Escoffier, B., Murat, C., Paschos, V.T. (2005). Probabilistic Coloring of Bipartite and Split Graphs. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2005. ICCSA 2005. Lecture Notes in Computer Science, vol 3483. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424925_23
Download citation
DOI: https://doi.org/10.1007/11424925_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25863-6
Online ISBN: 978-3-540-32309-9
eBook Packages: Computer ScienceComputer Science (R0)