Steiner minimal trees in \(L^ 2_ p\)
type: Item
instance of: scholarly article
title: Steiner minimal trees in \(L^ 2_ p\)
zbMATH Open document ID: 0863.05026
DOI: 10.1016/0012-365X(94)00368-S
published in: Discrete Mathematics
publication date: 1997-05-28T00:00:00Z
review text: The shortest trees for finite sets of points in \(L^2_p\), where \(L^2_p\) is the affine plane with norm \(|(x,y) |_p = (|x|^p + |y|^p)^{1/p}\) for \(1\leq p< \infty\), are studied. These trees are called Steiner minimum trees. A Steiner minimum tree may contain vertices other then the given points. Those additional vertices are called Steiner points. The authors also consider the shortest tree with restriction that the number of Steiner points is at most \(k\). Such a tree is called a \(k\)-Steiner minimum tree. This paper is a survey on the Steiner minimum trees and the \(k\)-Steiner minimum trees in \(L^2_p\).
reviewed by: Du Ding-Zhu
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 932524
zbMATH Keywords: \(k\)-Steiner minimum tree
zbMATH Keywords: Steiner minimum trees
zbMATH Keywords: Steiner points
author: Dietmar Cieslik
author: Johann Linhart
MaRDI profile type: Publication
cites work: An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
cites work: Finding Minimum Spanning Trees
cites work: Q3689203
cites work: The Fermat-Steiner-Weber-problem in Minkowski spaces
cites work: Q3970498
cites work: Q3484850
cites work: Q3972515
cites work: The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
cites work: On Steiner minimal trees with \(L_ p\) distance
cites work: Weber's problem and weiszfeld's algorithm in general spaces
cites work: The Complexity of Computing Steiner Minimal Trees
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: The 1-steiner tree problem
cites work: Steiner Minimal Trees
cites work: On the History of the Minimum Spanning Tree Problem
cites work: On Steiner’s Problem with Rectilinear Distance
cites work: On Steiner Minimal Trees with Rectilinear Distance
cites work: Selected Families of Location Problems
cites work: Two-Dimensional Voronoi Diagrams in the L p -Metric
cites work: Modelling Inter-city Road Distances by Mathematical Functions
cites work: An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
cites work: Technical Note—Minisum Ip Distance Location Problems Solved via a Perturbed Problem and Weiszfeld's Algorithm
full work available at URL: 0012-365x(94)00368-s
OpenAlex ID: W2034971340
description: scientific article; zbMATH DE number 932524