Computational complexity of edge modification problems in different classes of graphs

BURZYN, PABLO; BONOMO, FLAVIA; DURÁN, GUILLERMO

Santiago

Conferencia; Latin-American Conference on Combinatorics, Graphs and Applications (LACGA); 2004

Universidad de Chile

Edge modification problems in graphs have a lot of applications in different areas. Polynomial time algorithms and NP-completeness results appear in several works in the literature. In this paper, we prove new complexity results of these problems in some graph classes, such as, interval, circular-arc, permutation, circle, bridge and weakly chordal graphs.