Distributed approximation of capacitated dominating sets
From MaRDI portal
Publication:613113
DOI10.1007/S00224-010-9271-XzbMATH Open1213.68694OpenAlexW2687257225MaRDI QIDQ613113FDOQ613113
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
Recommendations
- Constant-time distributed dominating set approximation
- Constant-time distributed dominating set approximation
- Distributed Dominating Set Approximations beyond Planar Graphs
- Deterministic distributed dominating set approximation in the CONGEST model
- Near-optimal distributed approximation of minimum-weight connected dominating set
- A distributed algorithm for \(k\)-dominating sets
- A distributed approximation algorithm for the bottleneck connected dominating set problem
- Distributed minimum dominating set approximations in restricted families of graphs
- A distributed algorithm to find \(k\)-dominating sets
- Distributed algorithms for \textsc{Edge Dominating Sets}
Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Generalized submodular cover problems and applications
- Complexity of network synchronization
- How to Allocate Network Centers
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Maximal independent sets in radio networks
- What cannot be computed locally!
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Low diameter graph decompositions
- Discrete mobile centers
- Distributed Computing
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Leveraging Linial’s Locality Limit
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- On the locality of bounded growth
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- The price of being near-sighted
- What Can be Computed Locally?
- Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
- Veracity radius
Cited In (9)
- Fast Distributed Approximation for Max-Cut
- Algorithmic Applications of Tree-Cut Width
- Deterministic distributed construction of \(T\)-dominating sets in time \(T\)
- Distributed Dominating Set Approximations beyond Planar Graphs
- Can we locally compute sparse connected subgraphs?
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Distributed minimum dominating set approximations in restricted families of graphs
- Distributed algorithms for covering, packing and maximum weighted matching
- Title not available (Why is that?)
This page was built for publication: Distributed approximation of capacitated dominating sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613113)
