Generalised k-Steiner tree problems in normed planes

DOI10.1007/S00453-013-9780-5MaRDI QIDQ2258073zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. Brazil, D. A. Thomas, C. J. Ras, Konrad J. Swanepoel

Publication date 2 March 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-Steiner treebottleneck Steiner problemnetwork optimisationpolynomial time algorithm

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within $O(n^2)$ time. In this paper we generalise their approach in order to solve the $k$-Steiner tree problem, in which the Steiner minimum tree may contain up to $k$ Steiner points for a given constant $k$. We also extend their approach further to encompass other normed planes, and to solve a much wider class of problems, including the $k$-bottleneck Steiner tree problem and other generalised $k$-Steiner tree problems. We show that, for any fixed $k$, such problems can be solved in $O(n^{2k})$ time.

Recommendations

• scientific article; zbMATH DE number 1182759
• Minimum Steiner trees in normed planes
• A note on the generalized Steiner tree polytope
• An approximation scheme for some Steiner tree problems in the plane
• scientific article; zbMATH DE number 1555959
• Some generalizations of the steiner problem in graphs
• k-Steiner-minimal-trees in metric spaces
• On the restricted k-Steiner tree problem
• Steiner trees in general nonuniform orientations
• Insight into the computation of Steiner minimal trees in Euclidean space of general dimension

Cites work

• A New Method for the Multifacility Minimax Location Problem
• Combinatorial optimization. Theory and algorithms.
• Degree-five Steiner points cannot reduce network costs for planar sets
• Exact algorithms for the bottleneck Steiner tree problem
• scientific article; zbMATH DE number 2107839 (Why is no real title available?)
• scientific article; zbMATH DE number 1424547 (Why is no real title available?)
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Optimal and approximate bottleneck Steiner trees
• Steiner trees for fixed orientation metrics
• The 1-steiner tree problem
• The shortest network under a given topology
• Transitions in geometric minimum spanning trees

Cited in

(8)

• On the restricted 1-Steiner tree problem
• On the restricted k-Steiner tree problem
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• The bottleneck 2-connected k-Steiner network problem for k 2
• An exact algorithm for the Euclidean k-Steiner tree problem
• An improved exact algorithm for the Euclidean k-Steiner tree problem
• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
• An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L_p planes

This page was built for publication: Generalised \(k\)-Steiner tree problems in normed planes

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