Computational complexity of edge modification problems in different classes of graphs
2004, Electronic Notes in Discrete Mathematics 18, 41-46, 2004Citas: 2
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Pablo Burzyn and Flavia Bonomo and Guillermo Durán
Abstract
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.