• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths

Bazgan, Cristina; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf; Stahlberg, Maximilian (2019), A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths, Networks, 73, 1, p. 23-37. 10.1002/net.21832

View/Open
More_Fine-Grained.pdf (268.2Kb)
Type
Article accepté pour publication ou publié
Date
2019
Journal name
Networks
Volume
73
Number
1
Publisher
Wiley
Pages
23-37
Publication identifier
10.1002/net.21832
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Fluschnik, Till
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Nichterlein, André
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Niedermeier, Rolf
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Stahlberg, Maximilian
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Abstract (EN)
We 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 studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem‐specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.
Subjects / Keywords
approximation algorithms; interdiction problems; length-bounded cuts; NP-hardness; parameterized complexity; special graph classes

Related items

Showing items related by title and author.

  • Thumbnail
    A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths 
    Bazgan, Cristina; Nichterlein, André; Niedermeier, Rolf (2015) Communication / Conférence
  • Thumbnail
    Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011) Communication / Conférence
  • Thumbnail
    Efficient determination of the k most vital edges for the minimum spanning tree problem 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2012) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of determining the most vital elements for the 1-median and 1-center location problems 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2010) Communication / Conférence
  • Thumbnail
    Complexity of determining the most vital elements for the p-median and p-center location problems 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo