How vulnerable is an undirected planar graph with respect to max flow

DOI10.1002/net.22205OpenAlexW4390586026MaRDI QIDQ6196897

Paolo Giulio Franciosa, Lorenzo Balzotti

Publication date: 15 March 2024

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22205

zbMATH Keywords

vitalityplanar graphsvulnerabilityundirected graphsmax flow

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random planar graphs and the London street network
• A linear-time algorithm for a special case of disjoint set union
• Planar maps as labeled mobiles
• Deterministic network interdiction
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Quantum Geometry
• Maximal Flow Through a Network
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Short path queries in planar graphs in constant time
• Maximum Flow in Planar Networks
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Finding the n Most Vital Links in Flow Networks
• A Faster Deterministic Maximum Flow Algorithm
• Max flow vitality in general and st‐planar graphs
• The network inhibition problem
• Improved algorithms for min cut and max flow in undirected planar graphs
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• Max flows in O(nm) time, or better
• Optimal interdiction of a supply network
• Network Analysis
• A Census of Planar Maps
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Faster shortest-path algorithms for planar graphs
• Non-crossing shortest paths lengths in planar graphs in linear time