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
approximation algorithmgraph theoryplanar graphsdistributed systemlogiclocal modelminimum dominating setfirst order definableconstant-factor approximationgraphs of bounded genuslocally embeddable graphs
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)
This page was built for publication: A Local Constant Factor MDS Approximation for Bounded Genus Graphs