Finding the most vital arcs in a network

DOI10.1016/0167-6377(89)90003-5zbMath0679.90086OpenAlexW1999293689MaRDI QIDQ1823164

Michael O. Ball, Rakesh V. Vohra, Bruce L. Golden

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90003-5

zbMATH Keywords

shortest path polynomial time algorithm lower bound NP- hard directed, double arc weighted network most vital arc

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items

A stochastic optimization model to reduce expected post-disaster response time through pre-disaster investment decisions, Dynamic vulnerability analysis of public transport networks: mitigation effects of real-time information, Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal, Application of Path Counting Problem and Survivability Function in Analysis of Social Systems, Applying path-counting methods for measuring the robustness of the network-structured system, Minimizing a stochastic maximum-reliability path, A class of algorithms for mixed-integer bilevel min-max optimization, Network interdiction via a critical disruption path: branch-and-price algorithms, Probability Distributions on Partially Ordered Sets and Network Interdiction Games, The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees, The k most vital arcs in the shortest path problem, Matching interdiction, An iterative security game for computing robust and adaptive network flows, Interdicting the activities of a linear program -- a parametric analysis, A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem, The stochastic critical node problem over trees, A survey on mixed-integer programming techniques in bilevel optimization, Finding the most vital node of a shortest path., Efficient algorithms for game-theoretic betweenness centrality, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Unnamed Item, On short paths interdiction problems: Total and node-wise limited interdiction, Finding the most vital edge with respect to minimum spanning tree in weighted graphs, On Algorithms Employing Treewidth for $L$-bounded Cut Problems, A bilevel programming model for proactive countermeasure selection in complex ICT systems, Modeling $s-t$ path availability to support disaster vulnerability assessment of network infrastructure, Super edge magic graceful graphs, The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs, Convex hull representation of the deterministic bipartite network interdiction problem, The most vital edges in the minimum spanning tree problem, Heuristics for multi-stage interdiction of stochastic networks, Connectivity interdiction, On the hardness of covering-interdiction problems, Sequential Shortest Path Interdiction with Incomplete Information, Finding an anti-risk path between two nodes in undirected graphs, A survey of network interdiction models and algorithms, The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms, Multilevel Approaches for the Critical Node Problem, The continuous maximum capacity path interdiction problem, Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire, The fuzzy shortest path problem and its most vital arcs, Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback, The single most vital arc in the most economical path problem -- a parametric analysis

Cites Work