Shortest trees and Steiner trees with rectilinear distances (Catalan)

Shortest trees and Steiner trees with rectilinear distances (Catalan)

0.00 Avg rating0 Votes
Article ID: iaor1990613
Country: Spain
Volume: 12
Issue: 2
Start Page Number: 159
End Page Number: 174
Publication Date: Mar 1988
Journal: QUESTIIO
Authors: ,
Abstract:

Given a set of points P in the plane and using the rectilinear distance, some points of view related to the classical problem of finding its shortest spanning tree are considered. First, the main properties of Steiner trees are reviewed, next, an upper bound is obtained for the length of any shortest spanning tree forma set P enclosed in a square of one unit side. Finally, a backtracking-based algorithm is developed which allows to find-when existing-a minimum-distance rectangle tree for any distribution P. These rectangle trees simplifies very much the task of looking for a Steiner tree. In fact, they allow the Steiner Tree Problem to become resoluble using a polynomial-time algorithm.

Reviews

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