Mostrar el registro sencillo del ítem
dc.contributor.author
do Forte, Vinicius L.
dc.contributor.author
Lin, Min Chih
dc.contributor.author
Lucena, Abilio
dc.contributor.author
Maculan, Nelson
dc.contributor.author
Moyano, Verónica Andrea
dc.contributor.author
Szwarcfiter, Jayme L.
dc.date.available
2019-12-26T18:27:41Z
dc.date.issued
2018-10
dc.identifier.citation
do Forte, Vinicius L.; Lin, Min Chih; Lucena, Abilio; Maculan, Nelson; Moyano, Verónica Andrea; et al.; Modelling and solving the perfect edge domination problem; Springer Heidelberg; Optimization Letters; 10-2018
dc.identifier.issn
1862-4472
dc.identifier.uri
http://hdl.handle.net/11336/92974
dc.description.abstract
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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Springer Heidelberg
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
COMPUTATIONAL RESULTS
dc.subject
EXACT ALGORITHMS
dc.subject
INSTANCE GENERATION
dc.subject
PERFECT EDGE DOMINATION
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Modelling and solving the perfect edge domination problem
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-12-16T19:13:41Z
dc.journal.pais
Alemania
dc.description.fil
Fil: do Forte, Vinicius L.. Universidade Federal Rural do Rio de Janeiro; Brasil
dc.description.fil
Fil: Lin, Min Chih. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina
dc.description.fil
Fil: Lucena, Abilio. Universidade Federal do Rio de Janeiro; Brasil
dc.description.fil
Fil: Maculan, Nelson. Universidade Federal do Rio de Janeiro; Brasil
dc.description.fil
Fil: Moyano, Verónica Andrea. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina
dc.description.fil
Fil: Szwarcfiter, Jayme L.. Universidade do Estado de Rio do Janeiro; Brasil. Universidade Federal do Rio de Janeiro; Brasil
dc.journal.title
Optimization Letters
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs11590-018-1335-x
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s11590-018-1335-x
Archivos asociados