Record number :
666031
Title of article :
ON THE PROPER INTERVALIZATION OF COLOREDCATERPILLAR TREES
Author/Authors :
Carme Alvarez and Maria Serna، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
20
From page :
667
To page :
686
Abstract :
This paper studies the computational complexity of theproper interval colored graph problem (picg), when the input graphis a colored caterpillar, parameterized by hair length. In order proveour result we establish a close relationship between the picg and agraph layout problem the proper colored layout problem (pclp). Weshow a dichotomy: the picg and the pclp are NP-complete for coloredcaterpillars of hair length ≥2, while both problems are in P for coloredcaterpillars of hair length <2. For the hardness results we provide areduction from the multiprocessor scheduling problem, while the polynomialtime results follow from a characterization in terms of forbiddensubgraphs
Keywords :
Complexity , caterpillar tree , graph layout problems , coloring
Journal title :
RAIRO - Theoretical Informatics and Applications
Serial Year :
2009
Link To Document :
بازگشت