Distributed approximation of capacitated dominating sets

DOI10.1007/S00224-010-9271-XMaRDI QIDQ613113zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

lower boundsdominating setslocalitycapacitiesdistributed approximationLP relaxation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed algorithms (68W15) Distributed systems (68M14)

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}

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Complexity of network synchronization
• Discrete mobile centers
• Distributed Computing
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Generalized submodular cover problems and applications
• How to Allocate Network Centers
• Leveraging Linial’s Locality Limit
• Locality in Distributed Graph Algorithms
• Low diameter graph decompositions
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On the locality of bounded growth
• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The price of being near-sighted
• Veracity radius, capturing the locality of distributed computations
• What Can be Computed Locally?
• What cannot be computed locally!
• \textsc{Maximal Independent Sets} in radio networks

Cited in

(9)

• Fast Distributed Approximation for Max-Cut
• Algorithmic applications of tree-cut width
• Space-efficient local computation algorithms
• 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

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)