The Hardness of intervalizing four colored caterpillars

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/84544

Title:	The Hardness of intervalizing four colored caterpillars
Author:	Serna Iglesias, María José; Díaz Iriberri, José; Álvarez Faura, M. del Carme
Other authors:	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.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Intervalizing colored graphs -ICG -DNA -Mapping
Rights:
Document type:	Article - Published version Report
Share: