Show simple item record

dc.contributor.authorPaschos, Stratos*
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2013-10-01T14:47:20Z
dc.date.available2013-10-01T14:47:20Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11742
dc.language.isoenen
dc.subjectapproximationen
dc.subjectreoptimizationen
dc.subjectminimum spanning treeen
dc.subject.ddc003en
dc.titleReoptimization of the minimum spanning treeen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe implement a fast reoptimization algorithm for MIN SPANNING TREE under vertex insertions, initially proposed and analyzed in the work of Boria and Paschos [Boria N, Paschos VTh. Fast reoptimization for the minimum spanning tree problem. J Discrete Algor 2010, 8:296–310] and study its experimental approximation behavior in randomly generated graphs. The reoptimization setting can briefly be formulated as follows: given an instance of the problem for which we already know some optimal solution, and given some ‘small’ perturbations on this instance, is it possible to compute a new (optimal or at least near-optimal) solution for the modified instance without computation from scratch? We focus in this article on the most popular modification: vertex-insertion.en
dc.relation.isversionofjnlnameWiley Interdisciplinary Reviews: Computational Statistics
dc.relation.isversionofjnlvol4en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages211-217en
dc.relation.isversionofdoi10.1002/wics.204en
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds*
hal.person.labIds989*
hal.identifierhal-01511877*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record