Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
From MaRDI portal
Publication:2575833
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
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
