|
 
|
[BP06] Feasible node colorings of trees with cardinality constraints
Rapport Scientifique : Date de dépot: 2006/01/01, (Tech. Rep.: CEDRIC-06-987)
motcle:
Résumé:
Given a tree T with n vertices and three nonnegative
integers (n1,n2,n3) such that n1+n2+n3=n, our goal is to
find a 3-coloring of T such that each color class i contains
ni nodes i=1,2,3. Using a dynamic programming approach we
show that this problem can be solved in time O(n5 log n). We
also show that our algorithm can be adapted to the case of
k-colorings for fixed k.
Commentaires:
Submitted
BibTeX
| @techreport { | |||
| BP06, | |||
| title | = | "{Feasible node colorings of trees with cardinality constraints}", | |
| author | = | "C. Bentz and C. Picouleau", | |
| number | = | "{CEDRIC-06-987}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2006}, | |
| note | = | "{Submitted}", | |
| } | |||
