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

DOI10.1002/NET.22205MaRDI QIDQ6196897zbMATH OpenOpenAlexFDO

Authors Lorenzo Balzotti, Paolo G. Franciosa

Publication date 15 March 2024

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

vitalityplanar graphsundirected graphsvulnerabilitymax flow

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• Max flow vitality in general and \(st\)-planar graphs
• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• Finding the \(k\) most vital elements of an s-t planar directed network
• Maximum Flow in Directed Planar Graphs with Vertex Capacities
• Maximum flow in directed planar graphs with vertex capacities

Cites work

• scientific article; zbMATH DE number 139786 (Why is no real title available?)
• scientific article; zbMATH DE number 795214 (Why is no real title available?)
• A Census of Planar Maps
• A Faster Deterministic Maximum Flow Algorithm
• A linear-time algorithm for a special case of disjoint set union
• An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
• Deterministic network interdiction
• Faster shortest-path algorithms for planar graphs
• Finding the n Most Vital Links in Flow Networks
• 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 flow vitality in general and \(st\)-planar graphs
• Max flows in \(O(nm)\) time, or better
• Maximal Flow Through a Network
• Maximum Flow in Planar Networks
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Multiple-source shortest paths in planar graphs
• Network Analysis
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Non-crossing shortest paths lengths in planar graphs in linear time
• Optimal interdiction of a supply network
• Planar maps as labeled mobiles
• Quantum Geometry
• Random planar graphs and the London street network
• Short path queries in planar graphs in constant time
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• The network inhibition problem

This page was built for publication: How vulnerable is an undirected planar graph with respect to max flow

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