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