• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

The hypocoloring problem: complexity and approximability results when the chromatic number is small

de Werra, Dominique; Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (2004), The hypocoloring problem: complexity and approximability results when the chromatic number is small, in Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard, Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Springer : Berlin, p. 377-388. http://dx.doi.org/10.1007/978-3-540-30559-0_32

View/Open
hypercoloring.pdf (169.5Kb)
Type
Communication / Conférence
Date
2004
Conference title
30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)
Conference date
2004-06
Conference city
Bad Honnef
Conference country
Allemagne
Book title
Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
Book author
Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3353
Published in
Berlin
ISBN
978-3-540-24132-4
Number of pages
404
Pages
377-388
Publication identifier
http://dx.doi.org/10.1007/978-3-540-30559-0_32
Metadata
Show full item record
Author(s)
de Werra, Dominique
Demange, Marc
Monnot, Jérôme cc
Paschos, Vangelis
Abstract (EN)
We consider a weighted version of the subcoloring problem that we call the hypocoloring problem: given a weighted graph G=(V,E;w) where w(v)S=(S1,¼,Sk)=(S1Sk) of the node set of G into hypostable sets and minimizing max{åv Î Kw(v)| K Î S}maxvKw(v) KS . Properties of hypocolorings are stated; complexity and approximability results are presented in some graph classes. The associated decision problem is shown to be NP-complete for bipartite graphs and triangle-free planar graphs with maximum degree 3. Polynomial algorithms are given for graphs with maximum degree 2 and for trees with maximum degree Delta.
Subjects / Keywords
Algorithms; Approximability; Complexity; Weighted graphs; Subcoloring problem

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    Weighted coloring on planar, bipartite and split graphs: complexity and approximation 
    Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
  • Thumbnail
    Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation 
    de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
  • Thumbnail
    Weighted node coloring: when stable sets are expensive 
    Demange, Marc; de Werra, Dominique; Monnot, Jérôme; Paschos, Vangelis (2002) Communication / Conférence
  • Thumbnail
    Differential approximation results for the Steiner tree problem 
    Monnot, Jérôme; Demange, Marc; Paschos, Vangelis (2003) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo