Constant-time distributed dominating set approximation

DOI10.1145/872035.872040MaRDI QIDQ5892133zbMATH OpenOpenAlexFDO

Authors Fabian Kuhn, Roger Wattenhofer

Publication date 4 September 2015

Published in Proceedings of the twenty-second annual symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/32917

zbMATH Keywords

ad-hoc networksapproximation algorithmsdistributed algorithmsdominating setslinear programming

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Approximation algorithms (68W25) Linear programming (90C05)

Recommendations

• Constant-time distributed dominating set approximation
• An efficient distributed algorithm for constructing small dominating sets
• Deterministic distributed dominating set approximation in the CONGEST model
• Near-optimal distributed approximation of minimum-weight connected dominating set
• A distributed algorithm to find \(k\)-dominating sets

Cited in

(22)

• A distributed algorithm to find \(k\)-dominating sets
• Leveraging Linial’s Locality Limit
• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed spanner approximation
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed graph algorithms and their complexity: an introduction
• An efficient distributed algorithm for constructing small dominating sets
• Deterministic distributed dominating set approximation in the CONGEST model
• Near-optimal distributed approximation of minimum-weight connected dominating set
• Approximation algorithms for channel allocation problems in broadcast networks
• Distributed MST for constant diameter graphs
• Constant-time distributed dominating set approximation
• Distributed distance-r covering problems on sparse high-girth graphs
• Beep-and-sleep: message and energy efficient set cover
• Beep-and-sleep: message and energy efficient set cover
• Distributed approximation of capacitated dominating sets
• Graph polynomials
• Linear-time dominating set construction and leader election using mobile agents
• Distributed algorithms for weighted problems in sparse graphs
• Distributed algorithms for random graphs
• An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs

This page was built for publication: Constant-time distributed dominating set approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892133)