Show simple item record

dc.contributor.authorMurat, Cécile
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorDella Croce, Federico
dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-05T08:45:39Z
dc.date.available2009-10-05T08:45:39Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2110
dc.language.isoenen
dc.subjectProbabilistic optimizationen
dc.subjectApproximation algorithmsen
dc.subjectGraph coloringen
dc.subject.ddc003en
dc.titleProbabilistic graph-coloring in bipartite and split graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDAI Politecnico di Torino;Italie
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol17en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2009-04
dc.relation.isversionofjnlpages274-311en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10878-007-9112-2en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringer Netherlandsen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record