zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Sequential and parallel algorithms for minimum flows. (English) Zbl 1139.90335
Summary: First, we present two classes of sequential algorithms for minimum flow problem: decreasing path algorithms and preflow algorithms. Then we describe another approach of the minimum flow problem, that consists of applying any maximum flow algorithm in a modified network. In section 5 we present several parallel preflow algorithms that solve the minimum flow problem. Finally, we present an application of the minimum flow problem.

90B10Network models, deterministic (optimization)
05C85Graph algorithms (graph theory)
68R10Graph theory in connection with computer science (including graph drawing)
90C35Programming involving graphs or networks
Full Text: DOI
[1] R. Ahuja, T. Magnanti and J. Orlin,Network Flows. Theory, al gorithms and applications, Prentice Hall, Inc, Englewood Cliffs, NJ, 1993. · Zbl 1201.90001
[2] R. Ahuja, T. Magnanti and J. Orlin,Some Recent Advances in Network Flows, SIAM Review33 (1990), 175--219. · Zbl 0732.90028 · doi:10.1137/1033048
[3] R. Ahuja and J. Orlin,A Fast and Simple Algorithm for the Maximum Flow Problem, Operation Research37 (1988), 748--759. · Zbl 0691.90024 · doi:10.1287/opre.37.5.748
[4] R. Ahuja, J. Orlin and R. Tarjan,Improved Time Bounds for the Maximum Flow Problem. SIAM Journal of Computing18 (1988), 939--954. · Zbl 0675.90029 · doi:10.1137/0218065
[5] A. V. Goldberg,Processor-efficient implementation of a maxim um flow algorithm, Information Processing Letters38 (1991), 179--185. · Zbl 0754.90024 · doi:10.1016/0020-0190(91)90097-2
[6] A. V. Goldberg,A New Max-Flow Algorithm, MIT, Cambridge, 1985.
[7] A. V. Goldberg and R. E. Tarjan,A New Approach to the Maximum Flow Problem, Journal of ACM35 (1988), 921--940. · Zbl 0661.90031 · doi:10.1145/48014.61051
[8] A. V. Goldberg and R. E. Tarjan,A Parallel Algorithm for Fin ding a Blocking Flow in an Acyclic Network, Information Processing Letters31 (1989), 265--271. · Zbl 0688.68034 · doi:10.1016/0020-0190(89)90084-7
[9] A. V. Karzanov,Determining the Maximum Flow in a Network by the Method of Preflows, Soviet. Math. Dokl.15 (1974), 434--437. · Zbl 0303.90014
[10] Y. Shiloach and U. Vishkin,An O (n 2 logn)parallel max-flow algorithm, J. Algorithms3 (1982) 128--146. · Zbl 0483.90044 · doi:10.1016/0196-6774(82)90013-X