Mostrar el registro sencillo del ítem
NP-completeness results for edge modification problems
Autor | dc.contributor.author | Burzyn, Pablo | |
Autor | dc.contributor.author | Bonomo, Flavia | es_CL |
Autor | dc.contributor.author | Durán Maggiolo, Guillermo | es_CL |
Fecha ingreso | dc.date.accessioned | 2008-12-15T11:43:17Z | |
Fecha disponible | dc.date.available | 2008-12-15T11:43:17Z | |
Fecha de publicación | dc.date.issued | 2006-08-15 | |
Cita de ítem | dc.identifier.citation | DISCRETE APPLIED MATHEMATICS Volume: 154 Issue: 13 Pages: 1824-1844 Published: AUG 15 2006 | en |
Identificador | dc.identifier.issn | 0166-218X | |
Identificador | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/124775 | |
Resumen | dc.description.abstract | The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different areas, and many polynomial-time algorithms and NP-completeness proofs for this kind of problems are known. In this work we prove new NP-completeness results for these problems in some graph classes, such as interval, circular-arc, permutation, circle, bridged, weakly chordal and clique-Helly graphs. | en |
Idioma | dc.language.iso | en | en |
Publicador | dc.publisher | ELSEVIER | en |
Palabras claves | dc.subject | CIRCULAR-ARC GRAPHS | en |
Título | dc.title | NP-completeness results for edge modification problems | en |
Tipo de documento | dc.type | Artículo de revista |
Descargar archivo
Este ítem aparece en la(s) siguiente(s) colección(ones)
-
Artículos de revistas
Artículos de revistas