HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5585
Title: An O(k℗n)-time algorithm for constructing an optimal rectilinear steiner tree for extremal point sets
Authors: Tang, Chi-keung
Issue Date: 1994
Abstract: A point set is extremal if and only if the points lie on the boundary of a rectilinear convex hull of the point set [l0]. For an extremal point set of size n, the problem of constructing an optimal rectilinear Steiner tree was first shown to be solvable in ο(n[to the power of 6]) time by Provan [9]. Later, Bern [3], and Erickson [6] developed a faster algorithm that runs in ο(n[to the power of 5]) time. Richards and Salowe [l0] developed an improved algorithm and solves the problem in ο(k[to the power of 4]n), where k is the number of sides of the rectilinear convex hull. Cheng et al. [4] observed a common substructure which often appears in an optimal Steiner tree and developed a dynamic programming algorithm that runs in ο(n[to the power of 3]) [4]. In the worst-case scenario, an extremal point set can have θ(n) boundary edges. So the algorithm in [4] has a better asymptotic time complexity than the algorithm given by Richards and Salowe. In this thesis, we make use of some of the results in [4] and [l0] and redesign a dynamic programming algorithm that runs in ο(k2n) time. Thus our algorithm has the best asymptotic time complexity known for the problem.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1994
60 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1994 Tang
URI: http://hdl.handle.net/1783.1/5585
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.