| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421002 | Discrete Applied Mathematics | 2006 | 21 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pablo Burzyn, Flavia Bonomo, Guillermo Durán,