Modelling and solving the perfect edge domination problem

A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exac...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	do Forte, V.L., Lin, M.C., Lucena, A., Maculan, N., Moyano, V.A., Szwarcfiter, J.L.
Formato:	INPR
Materias:	Computational results Exact algorithms Instance generation Perfect edge domination Optimization Domination problem Feasible solution Mathematical formulation Optimality Control engineering
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_18624472_v_n_p_doForte
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_18624472_v_n_p_doForte
record_format	dspace
spelling	todo:paper_18624472_v_n_p_doForte2023-10-03T16:33:23Z Modelling and solving the perfect edge domination problem do Forte, V.L. Lin, M.C. Lucena, A. Maculan, N. Moyano, V.A. Szwarcfiter, J.L. Computational results Exact algorithms Instance generation Perfect edge domination Optimization Computational results Domination problem Exact algorithms Feasible solution Instance generation Mathematical formulation Optimality Perfect edge domination Control engineering A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exact algorithm for the problem. Furthermore, testing our algorithms also represented a challenge. Standard randomly generated graphs tend to contain a single perfect edge dominating solution, i.e., the trivial one, containing all edges in the graph. Accordingly, some quite elaborated procedures had to be devised to have access to more challenging instances. A total of 736 graphs were thus generated, all of them containing feasible solutions other than the trivial ones. Every graph giving rise to a weighted and a non weighted instance, all instances solved to proven optimality by two of the algorithms tested. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature. INPR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_18624472_v_n_p_doForte
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 results Exact algorithms Instance generation Perfect edge domination Optimization Computational results Domination problem Exact algorithms Feasible solution Instance generation Mathematical formulation Optimality Perfect edge domination Control engineering
spellingShingle	Computational results Exact algorithms Instance generation Perfect edge domination Optimization Computational results Domination problem Exact algorithms Feasible solution Instance generation Mathematical formulation Optimality Perfect edge domination Control engineering do Forte, V.L. Lin, M.C. Lucena, A. Maculan, N. Moyano, V.A. Szwarcfiter, J.L. Modelling and solving the perfect edge domination problem
topic_facet	Computational results Exact algorithms Instance generation Perfect edge domination Optimization Computational results Domination problem Exact algorithms Feasible solution Instance generation Mathematical formulation Optimality Perfect edge domination Control engineering
description	A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exact algorithm for the problem. Furthermore, testing our algorithms also represented a challenge. Standard randomly generated graphs tend to contain a single perfect edge dominating solution, i.e., the trivial one, containing all edges in the graph. Accordingly, some quite elaborated procedures had to be devised to have access to more challenging instances. A total of 736 graphs were thus generated, all of them containing feasible solutions other than the trivial ones. Every graph giving rise to a weighted and a non weighted instance, all instances solved to proven optimality by two of the algorithms tested. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature.
format	INPR
author	do Forte, V.L. Lin, M.C. Lucena, A. Maculan, N. Moyano, V.A. Szwarcfiter, J.L.
author_facet	do Forte, V.L. Lin, M.C. Lucena, A. Maculan, N. Moyano, V.A. Szwarcfiter, J.L.
author_sort	do Forte, V.L.
title	Modelling and solving the perfect edge domination problem
title_short	Modelling and solving the perfect edge domination problem
title_full	Modelling and solving the perfect edge domination problem
title_fullStr	Modelling and solving the perfect edge domination problem
title_full_unstemmed	Modelling and solving the perfect edge domination problem
title_sort	modelling and solving the perfect edge domination problem
url	http://hdl.handle.net/20.500.12110/paper_18624472_v_n_p_doForte
work_keys_str_mv	AT dofortevl modellingandsolvingtheperfectedgedominationproblem AT linmc modellingandsolvingtheperfectedgedominationproblem AT lucenaa modellingandsolvingtheperfectedgedominationproblem AT maculann modellingandsolvingtheperfectedgedominationproblem AT moyanova modellingandsolvingtheperfectedgedominationproblem AT szwarcfiterjl modellingandsolvingtheperfectedgedominationproblem
_version_	1807322898665308160

Modelling and solving the perfect edge domination problem

Ejemplares similares