The Hardness of intervalizing four colored caterpillars

Consultar RECERCAT

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

Título:	The Hardness of intervalizing four colored caterpillars
Autor/a:	Serna Iglesias, María José; Díaz Iriberri, José; Álvarez Faura, M. del Carme
Otros autores:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	The problem of Intervalizing Colored Graphs (ICG) has received a lot of attention due to their use as a model for DNA physical mapping with ambiguous data. If k is the number of colors, the problem is known to be NP-Complete for general graphs for k>3 and has polynomial time algorithms for k=2 and k=3. In this paper we show that the ICG problem is NP-complete when the graph is a caterpillar tree, colored with k=4 (or more) colors, strengthen the cases for which the problem remains difficult.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Intervalizing colored graphs -ICG -DNA -Mapping
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Álvarez Faura, M. del Carme; Serna Iglesias, María José

Álvarez Faura, M. del Carme; Díaz Cort, Josep; Dieter Wilhelm, Mitsche; Serna Iglesias, María José

Álvarez Faura, M. del Carme; Díaz Cort, Josep; Serna Iglesias, María José

Álvarez Faura, M. del Carme; Serna Iglesias, María José

Álvarez Faura, M. del Carme; Cases Muñoz, Rafel; Díaz Cort, Josep; Petit Silvestre, Jordi; Serna Iglesias, María José

Coordinación

Patrocinio