Approximation schemes for wireless networks

DOI10.1145/1383369.1383380zbMath1445.68173OpenAlexW2147465311MaRDI QIDQ4962754

Tim Nieberg, Walter Kern, Johann L. Hurink

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1383369.1383380

zbMATH Keywords

maximum independent setPTASwireless ad-hoc networksbounded growthminimum dominating set

Mathematics Subject Classification ID

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

Related Items

Sparse hop spanners for unit disk graphs, Linear-Time Approximation Algorithms for Unit Disk Graphs, A polynomial-time approximation to a minimum dominating set in a graph, Efficient independent set approximation in unit disk graphs, PTAS for the minimum weighted dominating set in growth bounded graphs, Polynomial time approximation schemes for minimum disk cover problems, A weakly robust PTAS for minimum clique partition in unit disk graphs, Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs, Unnamed Item, Wireless networking, dominating and packing, Shifting strategy for geometric graphs without geometry, Efficient sub-5 approximations for minimum dominating sets in unit disk graphs, Approximation algorithms for intersection graphs, Minimum clique partition in unit disk graphs, Dominating set of rectangles intersecting a straight line