Improving time bounds on maximum generalised flow computations by contracting the network

DOI10.1016/S0304-3975(03)00403-1zbMath1071.90010MaRDI QIDQ1884873

Tomasz Radzik

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Network flows; Flows with gains and losses; Generalised flows

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90B10: Deterministic network models in operations research

Related Items

A simple GAP-canceling algorithm for the generalized maximum flow problem, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines

Cites Work

• Speeding up Karmarkar's algorithm for multicommodity flows
• Optimum flows in general communication networks
• Faster Algorithms for the Generalized Network Flow Problem
• A polynomial combinatorial algorithm for generalized minimum cost flow
• Finding Minimum-Cost Circulations by Successive Approximation
• Combinatorial Algorithms for the Generalized Circulation Problem
• Self-adjusting binary search trees
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• A Faster Combinatorial Algorithm for the Generalized Circulation Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item