Advertisement

Distance-k Information in Self-stabilizing Algorithms

  • Wayne Goddard
  • Stephen T. Hedetniemi
  • David P. Jacobs
  • Vilmar Trevisan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

Abstract

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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Comm. ACM 17(11), 643–644 (1974)zbMATHCrossRefGoogle Scholar
  2. 2.
    Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)zbMATHGoogle Scholar
  3. 3.
    Gairing, M., Goddard, W., Hedetniemi, S.T., Kristiansen, P., McRae, A.A.: Distance-two information in self-stabilizing algorithms. Parallel Process. Lett. 14, 387–398 (2004)CrossRefMathSciNetGoogle Scholar
  4. 4.
    Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: Self-stabilizing global optimization algorithms for large network graphs. Int. J. Dist. Sensor Net. 1, 329–344 (2005)CrossRefGoogle Scholar
  5. 5.
    Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)Google Scholar
  6. 6.
    Hedetniemi, S.M., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl. 46, 805–811 (2003)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Wayne Goddard
    • 1
  • Stephen T. Hedetniemi
    • 1
  • David P. Jacobs
    • 1
  • Vilmar Trevisan
    • 2
  1. 1.Department of Computer ScienceClemson UniversityUSA
  2. 2.Instituto de MatemáticaUFRGSPorto AlegreBrazil

Personalised recommendations