Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorNichterlein, André
dc.contributor.authorNiedermeier, Rolf
dc.date.accessioned2017-01-10T15:15:44Z
dc.date.available2017-01-10T15:15:44Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16145
dc.descriptionin Springer series Lecture Notes in Computer Science, Vol. 9079en
dc.language.isoenen
dc.subjectshortest pathen
dc.subjectparameterized complexityen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleA Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Pathsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study the NP-hard Shortest Path Most Vital Edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest st-path as much as possible. This scenario has been mostly studied from the viewpoint of approximation algorithms and heuristics, while we particularly introduce a parameterized and multivariate point of view. We derive refined tractability as well as hardness results, and identify numerous directions for future research. Among other things, we show that increasing the shortest path length by at least one is much easier than to increase it by at least two.en
dc.identifier.citationpages47-60en
dc.relation.ispartoftitleAlgorithms and Complexityen
dc.relation.ispartofeditorPaschos, Vangelis Th.
dc.relation.ispartofeditorWidmayer, Peter
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2015-05
dc.relation.ispartofpages430en
dc.relation.ispartofurl10.1007/978-3-319-18173-8en
dc.contributor.countryeditoruniversityotherGERMANY
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-18172-1en
dc.relation.conftitle9th International Conference - CIAC 2015en
dc.relation.confdate2015-05
dc.relation.confcityParisen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-18173-8_3en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-10T13:36:09Z
hal.person.labIds989
hal.person.labIds84325
hal.person.labIds84325
hal.identifierhal-01431247*


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