Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/96513
Título:
|
Intervalizing colored graphs is NP-complete for caterpilars with hair length 2
|
Autor/a:
|
Álvarez Faura, M. del Carme; Díaz Cort, Josep; Serna Iglesias, María José
|
Otros autores:
|
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. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Colored graphs intervalizing -Caterpillars |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|
Mostrar el registro completo del ítem