Distributed approximation of capacitated dominating sets
From MaRDI portal
Publication:613113
DOI10.1007/s00224-010-9271-xzbMath1213.68694OpenAlexW2687257225MaRDI QIDQ613113
Fabian Kuhn, Thomas Moscibroda
Publication date: 17 December 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-010-9271-x
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (8)
Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Fast Distributed Approximation for Max-Cut ⋮ Can we locally compute sparse connected subgraphs? ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Low diameter graph decompositions
- Discrete mobile centers
- Generalized submodular cover problems and applications
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Leveraging Linial’s Locality Limit
- The price of being near-sighted
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Complexity of network synchronization
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- How to Allocate Network Centers
- What Can be Computed Locally?
- On the locality of bounded growth
- Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
- Maximal independent sets in radio networks
- Veracity radius
- Distributed Computing
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- What cannot be computed locally!
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
This page was built for publication: Distributed approximation of capacitated dominating sets