|
Title:
|
On the proper intervalization of colored caterpillar trees
|
|
Author:
|
Álvarez Faura, M. del Carme; Serna Iglesias, María José
|
|
Other authors:
|
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. |
|
Subject(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 |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Article |
|
Share:
|
|
