skip to main content
10.1145/2016039.2016120acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
poster

A self-stabilizing algorithm for two disjoint minimal dominating sets in an arbitrary graph

Published:24 March 2011Publication History

ABSTRACT

In this paper, we present a self-stabilizing algorithm that concurrently finds two disjoint minimal dominating sets in an arbitrary network graph without any isolated node. The worst case convergence time of the algorithm from any arbitrary initial state is O(n4) where n is the number of nodes in the network.

References

  1. Attiya, H. and Welch, J. 1998. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, Hightstown, NJ. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Dolev, S., Israeli, A., and Moran, S. 1993. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7 (1993), 3--16. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Estrin, D., Govindan, R., Heidemann, J. S, and Kumar, S. 1999. Next century challenges: Scalable coordination in sensor networks. In Mobile Computing and Networking, pages 263--270, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Hedetniemi, S. M., Hedetniemi, S. T., Jacobs, D. P., and Srimani, P. K. 2003. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Computers & Mathematics with Applications, 46, 5--6 (2003), 805--811.Google ScholarGoogle ScholarCross RefCross Ref
  5. Ore, O. Theory of Graphs. 1962. American Mathematical Society, XXXVIII, Providence, R. I.Google ScholarGoogle Scholar

Index Terms

  1. A self-stabilizing algorithm for two disjoint minimal dominating sets in an arbitrary graph

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          ACM-SE '11: Proceedings of the 49th Annual Southeast Regional Conference
          March 2011
          399 pages
          ISBN:9781450306867
          DOI:10.1145/2016039

          Copyright © 2011 Authors

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 24 March 2011

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • poster

          Acceptance Rates

          Overall Acceptance Rate134of240submissions,56%
        • Article Metrics

          • Downloads (Last 12 months)0
          • Downloads (Last 6 weeks)0

          Other Metrics

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader