Enabling minimal dominating set in highly dynamic distributed systems

DOI10.1007/978-3-319-21741-3_4MaRDI QIDQ5207898zbMATH OpenOpenAlexFDO

Authors Swan Dubois, Mohamed-Hamza Kaaouachi, Franck Petit

Publication date 14 January 2020

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00378

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: We address the problem of computing a Minimal Dominating Set in highly dynamic distributed systems. We assume weak connectivity, i.e., the network may be disconnected at each time instant and topological changes are unpredictable. We make only weak assumptions on the communication: every process is infinitely often able to communicate with other processes (not necessarily directly). Our contribution is threefold. First, we propose a new definition of minimal dominating set suitable for the context of time-varying graphs that seems more relevant than existing ones. Next, we provide a necessary and sufficient topological condition for the existence of a deterministic algorithm for minimal dominating set construction in our settings. Finally, we propose a new measure of time complexity in time-varying graph in order to to allow fair comparison between algorithms. Indeed, this measure takes account of communication delays attributable to dynamicity of the graph and not to the algorithms.

Recommendations

• An efficient distributed algorithm for constructing small dominating sets
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• New self-stabilizing algorithms for minimal weakly connected dominating sets
• Self-stabilizing algorithm for minimal dominating set with safe convergence in an arbitrary graph
• Linear-time self-stabilizing algorithms for minimal domination in graphs

Cites work

• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• Algorithms on evolving graphs
• An optimal maximal independent set algorithm for bounded-independence graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Coloring unstructured wireless multi-hop networks
• Coordinated consensus in dynamic networks
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• Distributed computation in dynamic networks
• Exploration of constantly connected dynamic graphs based on cactuses

Cited in

(3)

• A tight bound on the number of mobile servers to guarantee transferability among dominating configurations
• Computing parameters of sequence-based dynamic graphs
• Robustness: a new form of heredity motivated by dynamic networks

This page was built for publication: Enabling minimal dominating set in highly dynamic distributed systems

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