A Local Constant Factor MDS Approximation for Bounded Genus Graphs

DOI10.1145/2933057.2933084zbMath1373.68301arXiv1602.02991OpenAlexW2488232363MaRDI QIDQ5361940

Stefan Schmid, Saeed Akhoondian Amiri, Sebastian Siebertz

Publication date: 29 September 2017

Published in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.02991

zbMATH Keywords

approximation algorithmgraph theoryplanar graphsdistributed systemlogiclocal modelminimum dominating setfirst order definableconstant-factor approximationgraphs of bounded genuslocally embeddable graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (12)

Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ 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 ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs ⋮ Local certification of graphs with bounded genus ⋮ Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: A Local Constant Factor MDS Approximation for Bounded Genus Graphs