Some Generalized Max-Flow Min-Cut Problems in the Plane

DOI10.1287/MOOR.16.2.310MaRDI QIDQ3978618zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock

Publication date 25 June 1992

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.16.2.310

zbMATH Keywords

\(\mathcal NP\)-completenessdamagesmax linkage problemmax-flow min-cutmin-break problemnetwork survivabilityplanar graphpolynomial algorithm

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 2075842
• Minimal disconnected cuts in planar graphs
• Minimal disconnected cuts in planar graphs
• The planar multiterminal cut problem
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

Cited in

(3)

• On multi-path routing for reliable communications in failure interdependent complex networks
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network

This page was built for publication: Some Generalized Max-Flow Min-Cut Problems in the Plane

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