Computational complexity of edge modification problems in different classes of graphs
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-ar...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p41_Burzyn |
| Aporte de: |
| Sumario: | 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. © 2004 Elsevier B.V. All rights reserved. |
|---|