Network flow interdiction on planar graphs

DOI10.1016/j.dam.2010.04.008zbMath1209.05117OpenAlexW2144824278MaRDI QIDQ987697

Rico Zenklusen

Publication date: 13 August 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.04.008

zbMATH Keywords

planar graphsnetwork robustnesspseudo-polynomial algorithmsnetwork flow interdictionplanar duality

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items (26)

Interdicting facilities in tree networks ⋮ Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Bounds of spectral radii on edge-most outer-planar bipartite graphs ⋮ A mixed-integer programming approach for locating jamming devices in a flow-jamming attack ⋮ Matching interdiction ⋮ Vertex downgrading to minimize connectivity ⋮ On designing networks resilient to clique blockers ⋮ Interdiction problems on planar graphs ⋮ Unnamed Item ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ A study of network violator interception based on a reliable game model ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ A bi-level model and memetic algorithm for arc interdiction location-routing problem ⋮ Unnamed Item ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Network flow interdiction on planar graphs ⋮ Maximum Capacity Path Interdiction Problem with Fixed Costs ⋮ Connectivity interdiction ⋮ On the hardness of covering-interdiction problems ⋮ Perfect matching interdiction problem restricted to a stable vertex ⋮ Multilevel Approaches for the Critical Node Problem ⋮ Using edge contractions to reduce the semitotal domination number ⋮ 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
• Network flow interdiction on planar graphs
• Clustering and domination in perfect graphs
• Flow in planar graphs with vertex capacities
• Deterministic network interdiction
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Stochastic Network Interdiction
• Reformulation and sampling to solve a stochastic network interdiction problem
• Maximal Flow Through a Network
• Finding the n Most Vital Links in Flow Networks
• Flow in Planar Graphs with Multiple Sources and Sinks
• The network inhibition problem
• Removing Arcs from a Network
• Optimal interdiction policy for a flow network
• Optimal interdiction of a supply network

This page was built for publication: Network flow interdiction on planar graphs