On short paths interdiction problems: Total and node-wise limited interdiction

DOI10.1007/s00224-007-9025-6zbMath1148.68036OpenAlexW2121815516MaRDI QIDQ929289

Vladimir A. Gurvich, Konrad Borys, Jihui Zhao, Endre Boros, Khaled M. Elbassioni, Gábor Rudolf

Publication date: 17 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9025-6

zbMATH Keywords

Approximation algorithmDijkstra's algorithmCyclic gameMaxmin mean cycleMinimal vertex coverMost vital arcs problemNetwork inhibitionNetwork interdiction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (49)

Interdicting facilities in tree networks ⋮ Minimum cost edge blocker clique problem ⋮ Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Minimum edge blocker dominating set problem ⋮ Critical edges/nodes for the minimum spanning tree problem: complexity and approximation ⋮ The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees ⋮ Matching interdiction ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Assistance and interdiction problems on interval graphs ⋮ On designing networks resilient to clique blockers ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Interdiction problems on planar graphs ⋮ Optimal controller synthesis for timed systems ⋮ Unnamed Item ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems ⋮ The stochastic interdiction median problem with disruption intensity levels ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost ⋮ Unnamed Item ⋮ Optimal Reachability in Divergent Weighted Timed Games ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ 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 ⋮ Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures ⋮ Blockers for the stability number and the chromatic number ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Cyclic games and linear programming ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ A bilevel programming model for proactive countermeasure selection in complex ICT systems ⋮ The critical node detection problem in networks: a survey ⋮ Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games ⋮ Blocking optimal structures ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Maximum Capacity Path Interdiction Problem with Fixed Costs ⋮ Connectivity interdiction ⋮ On the hardness of covering-interdiction problems ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ On relevant equilibria in reachability games ⋮ A decomposition approach for stochastic shortest-path network interdiction with goal threshold ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Multilevel Approaches for the Critical Node Problem ⋮ Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cyclical games with prohibitions
• On the hardness of approximating minimum vertex cover
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• The k most vital arcs in the shortest path problem
• Most vital links and nodes in weighted networks
• Positional strategies for mean payoff games
• Interpolation of functions over a measure space and conjectures about memory
• Extensions of two person zero sum games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Deterministic network interdiction
• Finding the most vital arcs in a network
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Mean Cost Cyclical Games
• Maximum-Minimum Sätze über Graphen
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• A deterministic subexponential algorithm for solving parity games
• Maximizing the minimum source-sink path subject to a budget constraint
• A problem in network interdiction
• Disjoint (s, t)‐cuts in a network
• Shortest-path network interdiction
• Two-Person Zero-Sum Games for Network Interdiction
• The network inhibition problem
• Optimal interdiction policy for a flow network
• Optimal interdiction of a supply network
• Automata, Languages and Programming

This page was built for publication: On short paths interdiction problems: Total and node-wise limited interdiction