Distance-k Information in Self-stabilizing Algorithms
- 401 Downloads
Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general polynomial transformation for constructing self-stabilizing algorithms which utilize distance-shape k knowledge, with a slowdown of n O(log k). Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. We also show how to find maximal k-packings in polynomial-time. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information.
Unable to display preview. Download preview PDF.
- 5.Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)Google Scholar