Show simple item record

dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-06T16:09:27Z
dc.date.available2010-04-06T16:09:27Z
dc.date.issued2010
dc.identifier.issn1570-8667
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3867
dc.language.isoenen
dc.subjectMinimum spanning tree
dc.subjectApproximation algorithms
dc.subjectReoptimization
dc.subject.ddc003en
dc.titleFast Reoptimization for the Minimum Spanning Tree Problem
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study reoptimization versions of the minimum spanning tree problem. The reoptimization setting can generally 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 ex nihilo computation? We focus on two kinds of modifications: node-insertions and node-deletions. When k new nodes are inserted together with their incident edges, we mainly propose a fast strategy with complexity O(kn) which provides a max{2,3−(2/(k−1))}-approximation ratio, in complete metric graphs and another one that is optimal with complexity O(nlogn). On the other hand, when k nodes are deleted, we devise a strategy which in O(n) achieves approximation ratio bounded above by 2left ceiling|Lmax|/2right ceiling in complete metric graphs, where Lmax is the longest deleted path and |Lmax| is the number of its edges. For any of the approximation strategies, we also provide lower bounds on their approximation ratios.
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol8
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages296-310
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.jda.2009.07.002
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2020-09-04T13:23:43Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record