Locally bounded k-colorings of trees
RAIRO - Operations Research (2009)
- Volume: 43, Issue: 1, page 27-33
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topBentz, C., and Picouleau, C.. "Locally bounded k-colorings of trees." RAIRO - Operations Research 43.1 (2009): 27-33. <http://eudml.org/doc/250639>.
@article{Bentz2009,
abstract = {
Given a tree T with n vertices, we show, by using a dynamic
programming approach, that the problem of finding a 3-coloring of
T respecting local (i.e., associated with p prespecified subsets
of vertices) color bounds can be solved in O(n6p-1logn)
time. We also show that our algorithm can be adapted to the case of
k-colorings for fixed k.
},
author = {Bentz, C., Picouleau, C.},
journal = {RAIRO - Operations Research},
keywords = {Bounded graph coloring; tree; dynamic programming.; bounded graph coloring; dynamic programming},
language = {eng},
month = {1},
number = {1},
pages = {27-33},
publisher = {EDP Sciences},
title = {Locally bounded k-colorings of trees},
url = {http://eudml.org/doc/250639},
volume = {43},
year = {2009},
}
TY - JOUR
AU - Bentz, C.
AU - Picouleau, C.
TI - Locally bounded k-colorings of trees
JO - RAIRO - Operations Research
DA - 2009/1//
PB - EDP Sciences
VL - 43
IS - 1
SP - 27
EP - 33
AB -
Given a tree T with n vertices, we show, by using a dynamic
programming approach, that the problem of finding a 3-coloring of
T respecting local (i.e., associated with p prespecified subsets
of vertices) color bounds can be solved in O(n6p-1logn)
time. We also show that our algorithm can be adapted to the case of
k-colorings for fixed k.
LA - eng
KW - Bounded graph coloring; tree; dynamic programming.; bounded graph coloring; dynamic programming
UR - http://eudml.org/doc/250639
ER -
References
top- B.S. Baker and E.G. Coffman, Mutual exclusion scheduling. Theor. Comput. Sci.162 (1996) 225–243.
- C. Berge, Graphes. Gauthier-Villars, Paris (1983).
- H.L. Bodlaender and F.V. Fomin, Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci.349 (2005) 22–30.
- H.L. Bodlaender and K. Jansen, Restrictions of graph partition problems. Part I. Theor. Comput. Sci.148 (1995) 93–109.
- B. Bollobás and R. Guy, Equitable and proportional coloring of trees. J. Comb. Theory, Ser. B34 (1983) 177–186.
- B.-L. Chen and K.-W. Lih, A note on the m-bounded chromatic number of a tree. Eur. J. Comb.14 (1993) 311–312.
- B.-L. Chen and K.-W. Lih, Equitable Coloring of Trees. J. Comb. Theory, Ser. B61 (1994) 83–87.
- T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms. The MIT press, (2001).
- D. de Werra, A. Hertz, D. Kobler and N.V.R. Mahadev, Feasible edge colorings of trees with cardinality constraints. Discrete Math.222 (2000) 61–72.
- M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness. Ed. Freeman New York (1979).
- S. Gravier, D. Kobler and W. Kubiak, Complexity of list coloring problems with a fixed total number of colors. Discrete Appl. Math.117 (2002) 65–79.
- A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős. Combinatorial Theory and its Applications, Vol. II, North-Holland, Amsterdam (1970) 601–623.
- P. Hansen, A. Hertz and J. Kuplinsky, Bounded vertex colorings of graphs. Discrete Math.111 (1993) 305–312.
- M. Jarvis and B. Zhou, Bounded vertex coloring of trees. Discrete Math.232 (2001) 145–151.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.