Journal article
Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
SIAM journal on computing, Vol.29(2), pp.600-614
01/1999
DOI: 10.1137/S0097539798427156
Abstract
Locating a center or a median in a graph is a fundamental graph-theoretic problem. Centers and medians are especially important in distributed systems because they are ideal locations for placing resources that need to be shared among different processes in a network. This paper presents simple self-stabilizing algorithms for locating centers and medians of trees. Since these algorithms are self-stabilizing, they can tolerate transient failures. In addition, they can automatically adjust to a dynamically changing tree topology. After the algorithms are presented, their correctness is proven and upper bounds on their time complexity are established. Finally, extensions of our algorithms to trees with arbitrary, positive edge costs are sketched.
Details
- Title: Subtitle
- Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
- Creators
- Steven C. BruellSukumar GhoshMehmet Hakan KaraataSriram V. Pemmaraju
- Resource Type
- Journal article
- Publication Details
- SIAM journal on computing, Vol.29(2), pp.600-614
- DOI
- 10.1137/S0097539798427156
- ISSN
- 0097-5397
- eISSN
- 1095-7111
- Language
- English
- Date published
- 01/1999
- Academic Unit
- Computer Science
- Record Identifier
- 9984259413102771
Metrics
6 Record Views