Finding a feasible flow in a strongly connected network

Bernhard Haeupler; Robert E. Tarjan

doi:10.1016/j.orl.2008.02.003

Finding a feasible flow in a strongly connected network

Bernhard Haeupler, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.

Original language	English (US)
Pages (from-to)	397-398
Number of pages	2
Journal	Operations Research Letters
Volume	36
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2008.02.003
State	Published - Jul 2008

All Science Journal Classification (ASJC) codes

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Keywords

Combinatorial algorithms
Feasible flow
Maximum flow
Network flow
Strongly connected network

Access to Document

10.1016/j.orl.2008.02.003

Cite this

@article{792c935551974f69a3c16501b5762821,

title = "Finding a feasible flow in a strongly connected network",

abstract = "We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.",

keywords = "Combinatorial algorithms, Feasible flow, Maximum flow, Network flow, Strongly connected network",

author = "Bernhard Haeupler and Tarjan, {Robert E.}",

year = "2008",

month = jul,

doi = "10.1016/j.orl.2008.02.003",

language = "English (US)",

volume = "36",

pages = "397--398",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Finding a feasible flow in a strongly connected network

AU - Haeupler, Bernhard

AU - Tarjan, Robert E.

PY - 2008/7

Y1 - 2008/7

N2 - We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.

AB - We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.

KW - Combinatorial algorithms

KW - Feasible flow

KW - Maximum flow

KW - Network flow

KW - Strongly connected network

UR - http://www.scopus.com/inward/record.url?scp=46449092397&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46449092397&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2008.02.003

DO - 10.1016/j.orl.2008.02.003

M3 - Article

AN - SCOPUS:46449092397

SN - 0167-6377

VL - 36

SP - 397

EP - 398

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

Finding a feasible flow in a strongly connected network

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this