Enabling minimal dominating set in highly dynamic distributed systems

DOI10.1007/978-3-319-21741-3_4zbMATH Open1428.68150arXiv1502.00378OpenAlexW1571766706MaRDI QIDQ5207898FDOQ5207898

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)

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.

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

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

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)

Cites Work

• Distributed computation in dynamic networks
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Title not available (Why is that?)
• Coordinated consensus in dynamic networks
• Algorithms on evolving graphs
• Coloring unstructured wireless multi-hop networks
• An optimal maximal independent set algorithm for bounded-independence graphs
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• 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)