Record Details

Self-stabilizing algorithms for finding centers and medians of trees

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Self-stabilizing algorithms for finding centers and medians of trees
 
Creator BRUELL, SC
GHOSH, S
KARAATA, MH
PEMMARAJU, SV
 
Subject network location problems
graphs
rings
center
distributed algorithm
median
self-stabilization
tree
 
Description 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.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:44:36Z
2011-12-26T12:58:26Z
2011-12-27T05:48:22Z
2011-08-29T05:44:36Z
2011-12-26T12:58:26Z
2011-12-27T05:48:22Z
1999
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 29(2), 600-614
0097-5397
http://dx.doi.org/10.1137/S0097539798427156
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11981
http://hdl.handle.net/10054/11981
 
Language en