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...

Descripción completa

Detalles Bibliográficos
Autores principales: Burzyn, Pablo, Bonomo, Flavia, Durán, Guillermo A.
Publicado: 2004
Materias:
computational complexity
edge modification problems
graph classes
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p41_Burzyn
http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p41_Burzyn
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v18_n_p41_Burzyn
record_format dspace
spelling paper:paper_15710653_v18_n_p41_Burzyn2023-06-08T16:24:22Z Computational complexity of edge modification problems in different classes of graphs Burzyn, Pablo Bonomo, Flavia Durán, Guillermo A. computational complexity edge modification problems graph classes 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. Fil:Burzyn, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2004 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p41_Burzyn http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p41_Burzyn
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic computational complexity
edge modification problems
graph classes
spellingShingle computational complexity
edge modification problems
graph classes
Burzyn, Pablo
Bonomo, Flavia
Durán, Guillermo A.
Computational complexity of edge modification problems in different classes of graphs
topic_facet computational complexity
edge modification problems
graph classes
description 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.
author Burzyn, Pablo
Bonomo, Flavia
Durán, Guillermo A.
author_facet Burzyn, Pablo
Bonomo, Flavia
Durán, Guillermo A.
author_sort Burzyn, Pablo
title Computational complexity of edge modification problems in different classes of graphs
title_short Computational complexity of edge modification problems in different classes of graphs
title_full Computational complexity of edge modification problems in different classes of graphs
title_fullStr Computational complexity of edge modification problems in different classes of graphs
title_full_unstemmed Computational complexity of edge modification problems in different classes of graphs
title_sort computational complexity of edge modification problems in different classes of graphs
publishDate 2004
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p41_Burzyn
http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p41_Burzyn
work_keys_str_mv AT burzynpablo computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs
AT bonomoflavia computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs
AT duranguillermoa computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs
_version_ 1768541629392617472

Ejemplares similares