Algorithms and complexity analysis for some flow problems

DOI10.1007/BF01240739MaRDI QIDQ1317482zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 4204092
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Strongly polynomial time algorithms for certain concave minimization problems on networks

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 432784 (Why is no real title available?)
• scientific article; zbMATH DE number 3156015 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• scientific article; zbMATH DE number 3322861 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A generalization of max flow—min cut
• A good algorithm for lexicographically optimal flows in multi-terminal networks
• A strongly polynomial minimum cost circulation algorithm
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Complexity of some parametric integer and network programming problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear programming is log-space hard for P
• Parametric Combinatorial Computing and a Problem of Program Module Distribution
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• The complexity of linear programming
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Two-Commodity Flow

Cited in

(10)

• Faster algorithms for next breakpoint and max value for parametric global minimum cuts
• Combinatorial approximation algorithms for generalized flow problems
• scientific article; zbMATH DE number 3906196 (Why is no real title available?)
• Algorithmic Properties of Millstream Systems
• scientific article; zbMATH DE number 3950169 (Why is no real title available?)
• scientific article; zbMATH DE number 4055051 (Why is no real title available?)
• Complexity of a classical flow restoration problem
• scientific article; zbMATH DE number 1418332 (Why is no real title available?)
• Algorithmic results for potential‐based flows: Easy and hard cases
• Hitting a path: a generalization of weighted connectivity via game theory

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

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