Connecting a set of circles with minimum sum of radii

DOI10.1016/j.comgeo.2017.06.002zbMath1380.05113arXiv1105.0791OpenAlexW2623275761MaRDI QIDQ1699280

Sándor P. Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph S. B. Mitchell, Ulrike Stege, Venkatesh Srinivasan, S. H. Whitesides, Erin Wolf Chambers

Publication date: 19 February 2018

Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

approximationupper and lower boundsNP-hardnessintersection graphsconnectivity problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40) Signed and weighted graphs (05C22)

Related Items (11)

On the Bounded-Hop Range Assignment Problem ⋮ Set it and forget it: approximating the set once strip cover problem ⋮ Changing of the guards: strip cover with duty cycling ⋮ Unnamed Item ⋮ Connecting a set of circles with minimum sum of radii ⋮ A note on minimum-sum coverage by aligned disks ⋮ Bounded-hop communication networks ⋮ ``Green barrier coverage with mobile sensors ⋮ Range assignment of base-stations maximizing coverage area without interference ⋮ Unnamed Item ⋮ Average case network lifetime on an interval with adjustable sensing ranges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmenting the connectivity of geometric graphs
• Connecting a set of circles with minimum sum of radii
• Minimum-energy broadcasting in static ad hoc wireless networks
• Clustering to minimize the sum of cluster diameters
• Reverse search for enumeration
• The minimum-area spanning tree problem
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Energy-efficient wireless network design
• On the hardness of range assignment problems
• Planar Formulae and Their Uses
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2005
• Approximation of geometric dispersion problems

This page was built for publication: Connecting a set of circles with minimum sum of radii