Algorithms and complexity analysis for some flow problems

DOI10.1007/BF01240739zbMath0795.68100OpenAlexW3137940023MaRDI QIDQ1317482

Edith Cohen, Nimrod Megiddo

Publication date: 11 September 1994

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parametric flowstrongly polynomialconstrained flowlinear- programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Hitting a path: a generalization of weighted connectivity via game theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Linear programming is log-space hard for P
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Complexity of some parametric integer and network programming problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Parametric Combinatorial Computing and a Problem of Program Module Distribution
• Linear Programming in Linear Time When the Dimension Is Fixed
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A good algorithm for lexicographically optimal flows in multi-terminal networks
• A generalization of max flow—min cut
• Two-Commodity Flow
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• A Fast Parametric Maximum Flow Algorithm and Applications
• The complexity of linear programming

This page was built for publication: Algorithms and complexity analysis for some flow problems