A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
From MaRDI portal
Publication:2445394
DOI10.1016/j.ipl.2013.11.008zbMath1284.68645OpenAlexW2078400655MaRDI QIDQ2445394
Publication date: 14 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2013.11.008
Analysis of algorithms (68W40) 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 (13)
Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Compact distributed certification of planar graphs ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Local planar domination revisited ⋮ Local certification of graphs with bounded genus ⋮ Constant round distributed domination on graph classes with bounded expansion
Cites Work
This page was built for publication: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
