A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem

DOI10.1016/J.TCS.2018.06.040MaRDI QIDQ1625600zbMATH OpenOpenAlexFDO

Authors Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore

Publication date 29 November 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.06.040

zbMATH Keywords

dominating setproof labeling schemeself-stabilizationunison

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing algorithm for minimal dominating set with safe convergence in an arbitrary graph
• scientific article; zbMATH DE number 2061538
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Linear-time self-stabilizing algorithms for minimal domination in graphs
• Self-stabilizing algorithm for two disjoint minimal dominating sets
• Fast, silent self-stabilizing distance-\(k\) independent dominating set construction

Cites work

• A self-stabilizing k-clustering algorithm for weighted graphs
• An O(n)-time self-stabilizing leader election algorithm
• Competitive self-stabilizing \(k\)-clustering
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Fast, silent self-stabilizing distance-\(k\) independent dominating set construction
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On probabilistic snap-stabilization
• Principles of distributed systems. 10th international conference, OPODIS 2006, Bordeaux, France, December 12--15, 2006. Proceedings
• Proof labeling schemes
• Robust self-stabilizing weight-based clustering algorithm
• Self-stabilization
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing leader election in polynomial steps
• Self-stabilizing systems in spite of distributed control
• Synchronous vs. asynchronous unison
• What Can be Computed Locally?
• When graph theory helps self-stabilization

Cited in

(4)

• Fast, silent self-stabilizing distance-\(k\) independent dominating set construction
• Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs
• scientific article; zbMATH DE number 2061538 (Why is no real title available?)
• Being efficient in time, space, and workload: a self-stabilizing unison and its consequences

This page was built for publication: A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625600)