Science and Technology Production
Congress
Authorship
Burzyn, Pablo
;
BONOMO, FLAVIA
;
Durán, Guillermo
Date
2004
Publishing House and Editing Place
ELSEVIER SCIENCE BV
ISSN
1571-0653
Summary
Information provided by the agent in
SIGEVA
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.
Key Words
Graph classesEdge modification problemsComputational complexity