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

DOI10.1007/S00453-003-1056-ZMaRDI QIDQ1879253zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Minimum Diameter Spanning Trees and Related Problems
• scientific article; zbMATH DE number 1436136
• scientific article; zbMATH DE number 1947054
• Facility location and the geometric minimum-diameter spanning tree.
• Minimum spanning trees in d dimensions

Cites work

• scientific article; zbMATH DE number 1947054 (Why is no real title available?)
• scientific article; zbMATH DE number 2119700 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Complexity of spanning tree problems: Part I
• Minimum Diameter Spanning Trees and Related Problems
• On the minimum diameter spanning tree problem
• Performance optimization of VLSI interconnect layout

Cited in

(12)

• Euclidean chains and their shortcuts
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• scientific article; zbMATH DE number 1947054 (Why is no real title available?)
• Minimum-sum dipolar spanning tree in \(\mathbb R^3\)
• Minimum diameter vertex-weighted Steiner tree
• Computing minimum dilation spanning trees in geometric graphs
• Reconfiguration of spanning trees with degree constraints or diameter constraints
• Minimum diameter cost-constrained Steiner trees
• Algorithms for the minimum diameter terminal Steiner tree problem
• Long plane trees
• Minimizing the diameter of a spanning tree for imprecise points
• Minimizing the diameter of a spanning tree for imprecise points

This page was built for publication: Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879253)