• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Weighted coloring: further complexity and approximability results

Thumbnail
View/Open
publi121.pdf (103.9Kb)
Date
2006
Dewey
Recherche opérationnelle
Sujet
Partial k-tree; Line graph of bipartite graphs; Interval graphs; Weighted coloring; NP-Complete problems; Approximation algorithms
Journal issue
Information Processing Letters
Volume
97
Number
3
Publication date
2006
Article pages
98-103
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ipl.2005.09.013
URI
https://basepub.dauphine.fr/handle/123456789/2128
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
Escoffier, Bruno
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Abstract (EN)
Given a vertex-weighted graph G = (V,E;w), w(v) ≥ 0 for any v ∈ V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S1...,Sk)=(S1Sk) of the vertex set V of G into stable sets and minimizing ∑ i = 1 k w(S i ) where the weight of S is defined as max{w(v) : v ∈ S}. In this paper, we keep on with the investigation of the complexity and the approximability of this problem by mainly answering one of the questions raised by D. J. Guan and X. Zhu (”A Coloring Problem for Weighted Graphs”, Inf. Process. Lett. 61(2):77-81 1997).

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.