Show simple item record

Weighted coloring on planar, bipartite and split graphs: complexity and approximation

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorDemange, Marc
dc.contributor.authorde Werra, Dominique
dc.date.accessioned2010-03-09T11:16:19Z
dc.date.available2010-03-09T11:16:19Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3665
dc.language.isoenen
dc.subjectGraph coloringen
dc.subjectWeighted node coloringen
dc.subjectWeighted edge coloringen
dc.subjectApproximabilityen
dc.subjectNP-completenessen
dc.subjectPlanar graphsen
dc.subjectBipartite graphsen
dc.subjectSplit graphsen
dc.subject.ddc003en
dc.titleWeighted coloring on planar, bipartite and split graphs: complexity and approximationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P8-free bipartite graphs, but polynomial for P5-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol157en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2009-02
dc.relation.isversionofjnlpages819-832en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2008.06.013en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
publi962.pdf
Size:
189.1Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record