An optimal algorithm for the Euclidean bottleneck full Steiner tree problem

DOI10.1016/J.COMGEO.2013.10.001zbMATH Open1280.05064arXiv1305.0172OpenAlexW2068598660MaRDI QIDQ390152FDOQ390152

Authors: Ahmad Biniaz, Anil Maheshwari, Michiel Smid 

Publication date: 22 January 2014

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

minimum spanning treeSteiner treebottleneck lengthYao graph

Mathematics Subject Classification ID

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

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)