Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction

DOI10.1007/11753728_24MaRDI QIDQ3434697zbMATH OpenOpenAlexFDO

Authors Jihui Zhao, Leonid G. Khachiyan, Vladimir Gurvich

Publication date 2 May 2007

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11753728_24

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35) Games involving graphs (91A43)

Recommendations

• On short paths interdiction problems: Total and node-wise limited interdiction
• Dynamic shortest-path interdiction
• Shortest-path network interdiction
• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms
• Network interdiction with asymmetric cost uncertainty

Cited in

(10)

• On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost
• Maximum Capacity Path Interdiction Problem with Fixed Costs
• A nested family of k-total effective rewards for positional games
• Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire
• Matching interdiction
• Markov decision processes and stochastic games with total effective payoff
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• On short paths interdiction problems: Total and node-wise limited interdiction
• Cyclic games and linear programming
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434697)