Parameterized Complexity of Edge Interdiction Problems

DOI10.1007/978-3-319-08783-2_15zbMath1423.68210arXiv1401.2532OpenAlexW1544421729MaRDI QIDQ2920456

Yash Raj Shrestha, Jiong Guo

Publication date: 26 September 2014

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

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Related Items (4)

A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ Parametric matroid interdiction ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths

This page was built for publication: Parameterized Complexity of Edge Interdiction Problems