Decomposition algorithms for locating minimal cuts in a network

DOI10.1007/BF01581046zbMath0475.90082OpenAlexW2014488609MaRDI QIDQ3931039

John J. Jarvis, Suleyman Tufekci

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581046

zbMATH Keywords

decomposition algorithmslower boundsworst case analysislarge directed networklocating minimal cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition algorithm for optimality problems in tree-structured networks
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Flow Switching Approach to the Maximum Flow Problem: I
• Multi-Terminal Network Flows
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• More pathological examples for network flow problems
• Optimum Network Partitioning
• Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows
• Minimal disconnecting sets in directed multi‐commodity networks