A local approximation algorithm for minimum dominating set problem in anonymous planar networks

DOI10.1007/s00446-015-0247-6zbMath1342.68351OpenAlexW1161997546MaRDI QIDQ748117

Wojciech Wawrzyniak

Publication date: 20 October 2015

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-015-0247-6

zbMATH Keywords

approximationdominating setplanar graphlocal algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (4)

Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ Invulnerability of planar two-tree networks ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Local certification of graphs with bounded genus

Cites Work

• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Survey of local algorithms
• Lower bounds for local approximation
• Brief Announcement: Distributed Approximations for the Semi-matching Problem
• Fast Distributed Approximations in Planar Graphs
• The price of being near-sighted
• Locality in Distributed Graph Algorithms
• What Can be Computed Locally?
• Distributed 2-Approximation Algorithm for the Semi-matching Problem
• Constant-time distributed dominating set approximation

This page was built for publication: A local approximation algorithm for minimum dominating set problem in anonymous planar networks