A Faster Combinatorial Algorithm for the Generalized Circulation Problem

31 July 1996

journal article
research article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 21 (3) , 529-539
https://doi.org/10.1287/moor.21.3.529

Abstract

This paper presents a modified version of Algorithm MCF proposed by Goldberg, Plotkin and Tardos for the generalized circulation problem. This new combinatorial algorithm has a worst-case complexity that is better than the complexities of the MCF and Fat-Path combinatorial algorithms of Goldberg, Plotkin, and Tardos (1991).

Keywords

This publication has 3 references indexed in Scilit:

Combinatorial Algorithms for the Generalized Circulation Problem
Mathematics of Operations Research, 1991
Polynomial algorithms in linear programming
USSR Computational Mathematics and Mathematical Physics, 1980
A note on two problems in connexion with graphs
Numerische Mathematik, 1959