Conference proceeding
Self-stabilizing algorithm for the maximum flow problem
Conference proceedings - Annual International Phoenix Conference on Computers and Communications, pp.8-14
01/01/1995
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 the first distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in a acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults and can automatically adjust to topology changes and to changes in other parameters of the problem. A slight modification of the original algorithm is also presented and it is conjectured that the new algorithm computes a maximum flow in arbitrary networks.
Details
- Title: Subtitle
- Self-stabilizing algorithm for the maximum flow problem
- Creators
- Sukumar GhoshArobinda GuptaSriram V Pemmaraju
- Resource Type
- Conference proceeding
- Publication Details
- Conference proceedings - Annual International Phoenix Conference on Computers and Communications, pp.8-14
- ISSN
- 0896-582X
- Language
- English
- Date published
- 01/01/1995
- Academic Unit
- Computer Science
- Record Identifier
- 9984259429602771
Metrics
49 Record Views