[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
rapid-communication

Self-stabilizing algorithm for two disjoint minimal dominating sets

Published: 01 July 2019 Publication History

Abstract

We propose a new self stabilizing algorithm to compute two mutually disjoint minimal dominating sets in an arbitrary graph G with no isolates (this is always possible due to famous Ore's theorem in [1] that says “In a graph having no isolated nodes, the complement of any minimal dominating set is a dominating set”). We use an unfair central daemon and unique ids of the nodes. The time complexity of our algorithm is O ( n 3 ), an improvement by a factor of n from that of [2], that uses same assumptions to design an O ( n 4 ) algorithm, where n is the number of nodes in G. The algorithm uses the concept of running two copies of an algorithm in an interleaving manner such that the state spaces of the two copies are always kept mutually disjoint. We expect our approach will prove useful in designing algorithms for other mutually disjoint predicates in a network graph.

Highlights

New self-stabilizing algorithm for two disjoint minimal dominating sets in a graph.
An improvement by a factor of n over the best existing algorithm [2].
Interleaving of two copies of an algorithm on mutually disjoint state subspaces.
Use of unique node IDs and unfair central daemon.
Worst case time complexity is O ( n 3 ) compared to O ( n 4 ) in [2].

References

[1]
O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 1962.
[2]
S.T. Hedetniemi, D.P. Jacobs, K.E. Kennedy, A theorem of ore and self-stabilizing algorithms for disjoint minimal dominating sets, Theor. Comput. Sci. 593 (2015) 132–138.
[3]
E.W. Dijkstra, Self-stabilizing systems in spite of distributed control, Commun. ACM 17 (11) (Nov. 1974) 643–644.
[4]
B. Han, W. Jia, Clustering wireless ad hoc networks with weakly connected dominating set, J. Parallel Distrib. Comput. 67 (6) (2007) 727–737.
[5]
J. Yu, N. Wang, G. Wang, Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks, J. Parallel Distrib. Comput. 72 (1) (2012) 35–47.
[6]
N. Guellati, H. Kheddouci, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs, J. Parallel Distrib. Comput. 70 (4) (2010) 406–415.
[7]
Justin Southey, Michael A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011) 217–234.
[8]
W. Klostermeyer, M.E. Messinger, A. Ayello, Disjoint dominating sets with a perfect matching, Discrete Math. Algorithms Appl. 9 (2017).
[9]
Michael A. Henning, Iztok Peterin, A characterization of graphs with disjoint total dominating sets, Ars Math. Contemp. 16 (2) (2019) 359–375.
[10]
S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets, Comput. Math. Appl. 46 (2003) 805–811.

Index Terms

  1. Self-stabilizing algorithm for two disjoint minimal dominating sets
        Index terms have been assigned to the content through auto-classification.

        Recommendations

        Comments

        Please enable JavaScript to view thecomments powered by Disqus.

        Information & Contributors

        Information

        Published In

        cover image Information Processing Letters
        Information Processing Letters  Volume 147, Issue C
        Jul 2019
        94 pages

        Publisher

        Elsevier North-Holland, Inc.

        United States

        Publication History

        Published: 01 July 2019

        Author Tags

        1. Self-stabilizing algorithm
        2. Minimal dominating set
        3. Mutually disjoint minimal dominating sets
        4. Graph algorithms

        Qualifiers

        • Rapid-communication

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • 0
          Total Citations
        • 0
          Total Downloads
        • Downloads (Last 12 months)0
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 20 Dec 2024

        Other Metrics

        Citations

        View Options

        View options

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media