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

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

Tomasz Radzik

Publication date: 27 October 2004

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00403-1

zbMATH Keywords

Network flowsFlows with gains and lossesGeneralised flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (4)

A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ Temporal flows in temporal networks ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Improving time bounds on maximum generalised flow computations by contracting the network