A simple proof of the planar rectilinear Steiner ratio

A simple proof of the planar rectilinear Steiner ratio

0.00 Avg rating0 Votes
Article ID: iaor19931157
Country: Netherlands
Volume: 12
Issue: 4
Start Page Number: 271
End Page Number: 274
Publication Date: Oct 1992
Journal: Operations Research Letters
Authors:
Keywords: Steiner problem
Abstract:

The rectilinear Steiner ratio is the worst-case ratio of the length of a rectilinear minimum spanning tree to the length of a rectilinear Steiner minimal tree. Hwang proved that the ratio for point sets in the plane is equ1. The paper provides a simple proof of the equ2-bound.

Reviews

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