INVESTIGADORES
BONOMO flavia
artículos
Título:
NP-completeness results for edge modification problems
Autor/es:
BURZYN, PABLO; BONOMO, FLAVIA; DURÁN, GUILLERMO
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
Elsevier
Referencias:
Año: 2006 vol. 154 p. 1824 - 1844
ISSN:
0166-218X
Resumen:
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.