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

Guardado en:

Detalles Bibliográficos
Autores principales:	Burzyn, P., Bonomo, F., Durán, G.
Formato:	JOUR
Materias:	computational complexity edge modification problems graph classes
Acceso en línea:	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	todo:paper_15710653_v18_n_p41_Burzyn
record_format	dspace
spelling	todo:paper_15710653_v18_n_p41_Burzyn2023-10-03T16:27:00Z Computational complexity of edge modification problems in different classes of graphs Burzyn, P. Bonomo, F. Durán, G. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, P. Bonomo, F. Durán, G. 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.
format	JOUR
author	Burzyn, P. Bonomo, F. Durán, G.
author_facet	Burzyn, P. Bonomo, F. Durán, G.
author_sort	Burzyn, P.
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
url	http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p41_Burzyn
work_keys_str_mv	AT burzynp computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs AT bonomof computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs AT durang computationalcomplexityofedgemodificationproblemsindifferentclassesofgraphs
_version_	1807316028608217088

Computational complexity of edge modification problems in different classes of graphs

Ejemplares similares