Distributed approximation of capacitated dominating sets

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

zbMATH Keywords

lower boundslocalitydominating setscapacitiesdistributed approximationLP relaxation

Mathematics Subject Classification ID

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