Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/10751

On the proper intervalization of colored caterpillar trees
Álvarez Faura, M. del Carme; Serna Iglesias, María José
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
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.
À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
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Álvarez Faura, M. del Carme; Duch Brown, Amalia; Serna Iglesias, María José; Thilikos Touloupas, Dimitrios
Álvarez Faura, M. del Carme; Díaz Cort, Josep; Petit Silvestre, Jordi; Rolim, José; Serna Iglesias, María José
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José