Journal article
A self-stabilizing algorithm for the maximum flow problem
Distributed computing, Vol.10(4), pp.167-180
07/28/1997
DOI: 10.1007/s004460050034
Abstract
The maximum flow problem is a fundamental problem in graph theory and combinatorial optimization with a variety of important applications. Known distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents a distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in an acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults. It can automatically adjust to topology changes and to changes in other parameters of the problem. The paper presents results obtained by extensively experimenting with the algorithm. Two main observations based on these results are (1) the algorithm requires fewer than n2 moves for almost all test cases and (2) the algorithm consistently performs at least as well as a distributed implementation of the well-known Goldberg-Tarjan algorithm for almost all test cases. The paper ends with the conjecture that the algorithm correctly computes a maximum flow even in networks that contain cycles.
Details
- Title: Subtitle
- A self-stabilizing algorithm for the maximum flow problem
- Creators
- Sukumar Ghosh - University of IowaArobinda Gupta - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Distributed computing, Vol.10(4), pp.167-180
- DOI
- 10.1007/s004460050034
- ISSN
- 0178-2770
- eISSN
- 1432-0452
- Language
- English
- Date published
- 07/28/1997
- Academic Unit
- Computer Science
- Record Identifier
- 9984259412302771
Metrics
24 Record Views