A tight lower bound for the Steiner ratio in Minkowski planes
type: Item
instance of: scholarly article
title: A tight lower bound for the Steiner ratio in Minkowski planes
zbMATH Open document ID: 0827.05019
DOI: 10.1016/0012-365X(95)00005-H
author: Biao Gao
author: Du Ding-Zhu
author: Ron Graham
published in: Discrete Mathematics
publication date: 1995-08-27T00:00:00Z
review text: A minimum Steiner tree for a given set of points in a metric space is a network interconnecting the points of the set having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of points in the space. The present paper shows that for any Minkowski plane (= two-dimensional Banach space) the Steiner ratio is at least \(2/3\). Since the plane with \(L_1\) metric has Steiner ratio \(2/3\) this inequality is best possible.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 46B20
zbMATH DE Number: 790749
zbMATH Keywords: Steiner tree
zbMATH Keywords: Steiner ratio
zbMATH Keywords: metric space
zbMATH Keywords: spanning tree
zbMATH Keywords: Minkowski plane
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
cites work: The structure of singularities in \(\Phi\)-minimizing networks in \({\mathbb{R}}^ 2\)
cites work: The Fermat problem in Minkowski spaces
cites work: Q3972515
cites work: On the Steiner Problem
cites work: On Steiner ratio conjectures
cites work: Minimum Steiner trees in normed planes
cites work: A proof of the Gilbert-Pollak conjecture on the Steiner ratio
cites work: Reducing the Steiner Problem in a Normed Space
cites work: The Complexity of Computing Steiner Minimal Trees
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Steiner Minimal Trees
cites work: Q4100104
cites work: On Steiner Minimal Trees with Rectilinear Distance
cites work: On Steiner minimal trees with \(L_ p\) distance
cites work: Q4097206
cites work: Locating the vertices of a steiner tree in an arbitrary metric space
description: scientific article; zbMATH DE number 790749