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