Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs

DOI10.1016/j.tcs.2019.12.027zbMath1436.68229OpenAlexW2998224451WikidataQ126407006 ScholiaQ126407006MaRDI QIDQ2290639

Marcin Witkowski, Wojciech Wawrzyniak, Andrzej Czygrinow, Michał Hanćkowiak

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.12.027

zbMATH Keywords

dominating setdistributed algorithmsbounded-genus graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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 distance domination in graphs with no \(K_{2,t}\)-minor ⋮ Domination and convexity problems in the target set selection model ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Sachs' linkless embedding conjecture
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Survey of local algorithms
• Fast Distributed Approximations in Planar Graphs
• Distributed Computing: A Locality-Sensitive Approach
• An efficient distributed algorithm for constructing small dominating sets
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs

This page was built for publication: Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs