Show simple item record

dc.contributor.authorDella Croce, Federico
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorMurat, Cécile
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-03-22T14:12:18Z
dc.date.available2011-03-22T14:12:18Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5792
dc.language.isoenen
dc.subjectPolynomial algorithmen
dc.subjectcoloring problemen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleProbabilistic coloring of bipartite and split graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages91-97en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3483
dc.relation.ispartoftitleComputational Science and Its Applications - ICCSA 2005 International Conference, Singapore, May 9-12, 2005, Proceedings, Part IVen
dc.relation.ispartofeditorGervasi, Osvaldo
dc.relation.ispartofeditorGavrilova, Marina
dc.relation.ispartofeditorKumar, Vipin
dc.relation.ispartofeditorLagana, Antonio
dc.relation.ispartofeditorLee, Heow Pueh
dc.relation.ispartofeditorMun, Youngsong
dc.relation.ispartofeditorTaniar, David
dc.relation.ispartofeditorTan, Chih Jeng Kenneth
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2005
dc.relation.ispartofpages1362en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/b136278en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-25863-6en
dc.relation.conftitleInternational Conference on Computational Science and Its Applications (ICCSA'05)en
dc.relation.confdate2005-05
dc.relation.confcitySingapouren
dc.relation.confcountrySingapouren
dc.identifier.doihttp://dx.doi.org/10.1007/11424925_23


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record