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

DOI10.1007/S00453-003-1056-ZzbMATH Open1138.68477DBLPjournals/algorithmica/SpriggsKBSS04OpenAlexW2086252334WikidataQ56970579 ScholiaQ56970579MaRDI QIDQ1879253FDOQ1879253

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

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

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)

Cites Work

• 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
• On the minimum diameter spanning tree problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of spanning tree problems: Part I
• Performance optimization of VLSI interconnect layout

Cited In (12)

• Euclidean chains and their shortcuts
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• Title not available (Why is that?)
• 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)