An optimal algorithm for the Euclidean bottleneck full Steiner tree problem

DOI10.1016/J.COMGEO.2013.10.001MaRDI QIDQ390152zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

minimum spanning treeSteiner treebottleneck lengthYao graph

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Abstract: Let $P$ and $S$ be two disjoint sets of $n$ and $m$ points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to $S$, in which each point of $P$ is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in $O((n+m)logm)$ time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.

Recommendations

• On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem
• On the Euclidean bottleneck full Steiner tree problem
• The Euclidean bottleneck full Steiner tree problem
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane

Cited in

(9)

• The Euclidean bottleneck full Steiner tree problem
• On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem
• Bottleneck bichromatic full Steiner trees
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Faster bottleneck non-crossing matchings of points in convex position
• On the hardness of full Steiner tree problems
• Euclidean Steiner trees optimal with respect to swapping 4-point subtrees
• On full bottleneck Steiner tree problem
• On the Euclidean bottleneck full Steiner tree problem

This page was built for publication: An optimal algorithm for the Euclidean bottleneck full Steiner tree problem

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