A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

DOI10.1007/978-3-319-18173-8_3zbMath1459.68152OpenAlexW2181839983MaRDI QIDQ2947009

Rolf Niedermeier, André Nichterlein, Cristina Bazgan

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18173-8_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees ⋮ Fractals for Kernelization Lower Bounds ⋮ Unnamed Item ⋮ Most vital vertices for the shortest \(s-t\) path problem: complexity and branch-and-cut algorithm ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Resilient capacity-aware routing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Fundamentals of parameterized complexity
• On short paths interdiction problems: Total and node-wise limited interdiction
• The k most vital arcs in the shortest path problem
• 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
• Parametrized complexity theory.
• Interdiction Problems on Planar Graphs
• New Races in Parameterized Algorithmics
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Parameterized Complexity of Edge Interdiction Problems
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Maximizing the minimum source-sink path subject to a budget constraint
• Shortest-path network interdiction
• A Fast Branching Algorithm for Cluster Vertex Deletion
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)