NP-completeness results for edge modification problems |
| |
| Authors: | Pablo Burzyn Flavia Bonomo Guillermo Durán |
| |
| Institution: | a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
b Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile |
| |
| 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. |
| |
| Keywords: | Computational complexity Edge modification problems Graph classes NP-completeness |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
