Name
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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1137/S0097539798427156 | SIAM J. Comput. |
Keywords | Field | DocType |
simple self-stabilizing algorithm,self-stabilizing algorithms,tree topology,fundamental graph-theoretic problem,finding centers,ideal location,different process,transient failure,positive edge cost,upper bound,time complexity,distributed algorithm,tree,self stabilization,median,center,distributed system | Graph theory,Discrete mathematics,Combinatorics,Tree (graph theory),Correctness,Algorithm,Self-stabilization,Network topology,Distributed algorithm,Time complexity,Mathematics,Median | Journal |
Volume | Issue | ISSN |
29 | 2 | 0097-5397 |
Citations | PageRank | References |
22 | 1.00 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steven C. Bruell | 1 | 142 | 29.83 |
| Sukumar Ghosh | 2 | 476 | 41.08 |
| Mehmet Hakan Karaata | 3 | 194 | 19.62 |
| Sriram V. Pemmaraju | 4 | 727 | 51.91 |