Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/93011
Título:
|
The Proper interval colored graph problem for caterpillar trees
|
Autor/a:
|
Álvarez Faura, M. del Carme; Serna Iglesias, María José
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
This paper studies the computational complexity of the Proper Interval Colored Graph problem (PICG), when the input graph
is a colored tree. We show that the problem is hard for the class of caterpillar trees.
To prove our result we make use of a close relationship between intervalizing problems and graph layout problems. We define
a graph layout problem the Proper Colored Layout Problem (PCLP). Although PCLP is not equivalent to PICG, by
transforming the input graph we will stablish a close relationship between both problems. The main result is that the PICG is
NP-complete for colored caterpillars of hair length 2 and in P for caterpillars of hair length 1 or 0. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -PICG -PCLP -Proper interval colored graph problem -Proper colored layout problem -Computational complexity |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|
Mostrar el registro completo del ítem