A variational approach to the Steiner network problem

A variational approach to the Steiner network problem

0.00 Avg rating0 Votes
Article ID: iaor19921089
Country: Switzerland
Volume: 33
Start Page Number: 481
End Page Number: 499
Publication Date: Nov 1991
Journal: Annals of Operations Research
Authors: ,
Keywords: Steiner problem
Abstract:

Suppose n points are given in the plane. Their coordinates form a 2n-vector X. To study the question of finding the shortest Steiner network S connecting these points, the authors allow X to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the cases n=4,5 are discussed. The variational approach was used by the authors to solve other cases of the ratio conjecture (n=6, see [11] and for arbitrary n points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. The authors have also solved Graham’s problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method.

Reviews

Required fields are marked *. Your email address will not be published.