Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree

DOI10.1007/s00453-003-1056-zzbMath1138.68477OpenAlexW2086252334WikidataQ56970579 ScholiaQ56970579MaRDI QIDQ1879253

Michael Segal, J. Mark Keil, Michael J. Spriggs, Sergei Bespamyatnikh, Jack Scott Snoeyink

Publication date: 22 September 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1056-z

zbMATH Keywords

Approximation algorithmMinimum diameter spanning treeGeometric graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Euclidean chains and their shortcuts, Reconfiguration of spanning trees with degree constraints or diameter constraints, Minimum diameter cost-constrained Steiner trees, Minimizing the diameter of a spanning tree for imprecise points, Algorithms for the minimum diameter terminal Steiner tree problem, Minimum diameter vertex-weighted Steiner tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the minimum diameter spanning tree problem
• Complexity of spanning tree problems: Part I
• Performance optimization of VLSI interconnect layout
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Minimum Diameter Spanning Trees and Related Problems
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields