NP-completeness results for edge modification problems

Author	dc.contributor.author	Burzyn, Pablo
Author	dc.contributor.author	Bonomo, Flavia	es_CL
Author	dc.contributor.author	Durán Maggiolo, Guillermo	es_CL
Admission date	dc.date.accessioned	2008-12-15T11:43:17Z
Available date	dc.date.available	2008-12-15T11:43:17Z
Publication date	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
Identifier	dc.identifier.issn	0166-218X
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/124775
Abstract	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
Lenguage	dc.language.iso	en	en
Publisher	dc.publisher	ELSEVIER	en
Keywords	dc.subject	CIRCULAR-ARC GRAPHS	en
Título	dc.title	NP-completeness results for edge modification problems	en
Document type	dc.type	Artículo de revista