Geodesic
On the proper intervalization of colored caterpillar trees
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 667-686

Voir la notice de l'article provenant de la source Numdam

MR

This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs.

DOI : 10.1051/ita/2009014
Classification : 68Q25, 68W10
Keywords: complexity, caterpillar tree, graph layout problems, coloring 
Àlvarez, Carme; Serna, Maria. On the proper intervalization of colored caterpillar trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 667-686. doi: 10.1051/ita/2009014
@article{ITA_2009__43_4_667_0,
     author = {\`Alvarez, Carme and Serna, Maria},
     title = {On the proper intervalization of colored caterpillar trees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {667--686},
     year = {2009},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {4},
     doi = {10.1051/ita/2009014},
     mrnumber = {2589988},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2009014/}
}
TY  - JOUR
AU  - Àlvarez, Carme
AU  - Serna, Maria
TI  - On the proper intervalization of colored caterpillar trees
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 667
EP  - 686
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2009014/
DO  - 10.1051/ita/2009014
LA  - en
ID  - ITA_2009__43_4_667_0
ER  - 
%0 Journal Article
%A Àlvarez, Carme
%A Serna, Maria
%T On the proper intervalization of colored caterpillar trees
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 667-686
%V 43
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2009014/
%R 10.1051/ita/2009014
%G en
%F ITA_2009__43_4_667_0

Cité par Sources :