| Issue |
RAIRO-Theor. Inf. Appl.
Volume 43, Number 4, October-December 2009
|
|
|---|---|---|
| Page(s) | 667 - 686 | |
| DOI | https://doi.org/10.1051/ita/2009014 | |
| Published online | 30 July 2009 | |
On the proper intervalization of colored caterpillar trees
ALBCOM Research Group, Departament de Llenguatges i Sistemes Informàtics,
Universitat Politècnica de Catalunya,
Campus Nord, Edifici Omega, C/ Jordi Girona Salgado 1-3,
08034 Barcelona, Spain; alvarez@lsi.upc.edu; mjserna@lsi.upc.edu
Received:
8
February
2007
Accepted:
14
May
2009
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.
Mathematics Subject Classification: 68Q25 / 68W10
Key words: Complexity / caterpillar tree / graph layout problems / coloring
© EDP Sciences, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.