A Faster Combinatorial Algorithm for the Generalized Circulation Problem

DOI10.1287/MOOR.21.3.529zbMATH Open0873.90100OpenAlexW2150492728MaRDI QIDQ4716922FDOQ4716922

Zhiying Jin, Donald Goldfarb

Publication date: 30 October 1997

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

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

zbMATH Keywords

worst-case complexitygeneralized circulation problemarc imbalancegeneralized maximum flowpseudo-flow augmentation

Mathematics Subject Classification ID

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

Cited In (7)

• A Strongly Polynomial Algorithm for Generalized Flow Maximization
• Combinatorial Algorithms for the Generalized Circulation Problem
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• Improving time bounds on maximum generalised flow computations by contracting the network
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• A new scaling algorithm for the minimum cost network flow problem
• Generalized maximum flow over time with intermediate storage

This page was built for publication: A Faster Combinatorial Algorithm for the Generalized Circulation Problem

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