Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

DOI10.1016/j.jcss.2005.04.002zbMath1085.68184OpenAlexW2143858321MaRDI QIDQ2575833

Alessandro Mei, Alessandro Panconesi, Aravind Srinivasan, Devdatt P. Dubhashi

Publication date: 7 December 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.04.002

zbMATH Keywords

ad hoc networksdominating sets

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (13)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Distributed strong diameter network decomposition ⋮ Rumor Spreading with No Dependence on Conductance ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Distributed reformation of core-based group-shared multicast trees in mobile ad hoc networks ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Distributed construction of purely additive spanners ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Weakly Connected Domination in Graphs ⋮ Testing equality under the local broadcast model

Cites Work

• Unnamed Item
• On sparse spanners of weighted graphs
• Low diameter graph decompositions
• Approximation algorithms for connected dominating sets
• A threshold of ln n for approximating set cover
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• On the hardness of approximating minimization problems
• Non-approximability results for optimization problems on bounded degree instances

This page was built for publication: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons