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

DOI10.1002/net.21832zbMath1407.90090arXiv1804.09155OpenAlexW2888538681WikidataQ129318730 ScholiaQ129318730MaRDI QIDQ4628044

André Nichterlein, Maximilian Stahlberg, Till Fluschnik, Rolf Niedermeier, Cristina Bazgan

Publication date: 6 March 2019

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.09155

zbMATH Keywords

approximation algorithmsNP-hardnessparameterized complexityspecial graph classeslength-bounded cutsinterdiction problems

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59) Reliability, availability, maintenance, inspection in operations research (90B25)

Related Items (8)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ Assistance and interdiction problems on interval graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Unnamed Item ⋮ Safety in \(s\)-\(t\) paths, trails and walks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On the connectivity of visibility graphs
• Interdiction problems on planar graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• Fixed-parameter algorithms for cluster vertex deletion
• A faster computation of the most vital edge of a shortest path
• Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
• Deterministic network interdiction
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Parameterized approximability of maximizing the spread of influence in networks
• New Races in Parameterized Algorithmics
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Parameterized Complexity of Edge Interdiction Problems
• Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Length-bounded cuts and flows
• The Recognition of Series Parallel Digraphs
• Maximizing the minimum source-sink path subject to a budget constraint
• A problem in network interdiction
• Fractals for Kernelization Lower Bounds
• On Algorithms Employing Treewidth for $L$-bounded Cut Problems
• The complexity of finding maximum disjoint paths with length constraints
• Shortest-path network interdiction
• Parallel algorithms for series parallel graphs and graphs with treewidth two
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)

This page was built for publication: A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths