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

Title:	Intervalizing colored graphs is NP-complete for caterpilars with hair length 2
Author:	Álvarez Faura, M. del Carme; Díaz Cort, Josep; Serna Iglesias, María José
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	The problem of Intervalizing Colored Graphs 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 kgeq 4 and has polynomial time algorithms for k=2 and k=3. In this paper we prove that the problem is NP-Complete for caterpillars with hairs of length at most 2. In the positive side we give polynomial time algorithms for the problem in the cases, caterpillars with hairs of length at most 1 and any number of colors and caterpillars with hairs of length at most 2 and a constant number of colors. It is the first time a problem has been shown NP-complete for the particular case of caterpillars of hairs of length at most 2.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Colored graphs intervalizing -Caterpillars
Rights:
Document type:	Article - Published version Report
Share:

Show full item record