Algorithms and complexity analysis for some flow problems

DOI10.1007/BF01240739zbMATH Open0795.68100OpenAlexW3137940023MaRDI QIDQ1317482FDOQ1317482

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

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

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)

Cites Work

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

Cited In (10)

• Faster algorithms for next breakpoint and max value for parametric global minimum cuts
• Combinatorial approximation algorithms for generalized flow problems
• Title not available (Why is that?)
• Algorithmic Properties of Millstream Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of a classical flow restoration problem
• Title not available (Why is that?)
• 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)