Show simple item record

dc.contributor.authorMurat, Cécile
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-17T15:14:08Z
dc.date.available2010-03-17T15:14:08Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3728
dc.language.isoenen
dc.subjectGraphen
dc.subjectApproximation algorithmen
dc.subjectNP-completeen
dc.subjectColoringen
dc.subject.ddc003en
dc.titleOn the probabilistic minimum coloring and minimum k-coloringen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study a robustness model for the minimum coloring problem, where any vertex vi of the input-graph G(V,E) has some presence probability pi. We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of V into independent sets S1,S2,…,Sk, that minimizes the quantity View the MathML source, where, for any independent set View the MathML source, f(Si)=1-∏vjset membership, variantSi(1-pj). We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min k-Coloring) is NP-hard, for any kgreater-or-equal, slanted3. We finally study Probabilistic Min Coloring and Probabilistic Min k-Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol154en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2006-03
dc.relation.isversionofjnlpages564-586en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2005.06.007en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record