Título:
|
On the proper intervalization of colored caterpillar trees
|
Autor/a:
|
Álvarez Faura, M. del Carme; Serna Iglesias, María José
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
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. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Parallel algorithms -Computational complexity -Complexity -Caterpillar tree -Graph layout problems -Coloring -Algorismes paral·lels -Complexitat computacional |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Artículo |
Compartir:
|
|