عنوان

A clustering-based algorithm for the Rectilinear Steiner Tree Problem

Number

TLpq230944273

.Language of Text, Soundtrack etc

انگلیسی

Title Proper

A clustering-based algorithm for the Rectilinear Steiner Tree Problem

General Material Designation

[Thesis]

First Statement of Responsibility

Y. K. Karimjee

Name of Publisher, Distributor, etc.

King Fahd University of Petroleum and Minerals (Saudi Arabia)

Date of Publication, Distribution, etc.

1994

Specific Material Designation and Extent of Item

113

Dissertation or thesis details and type of degree

M.S.

Body granting the degree

King Fahd University of Petroleum and Minerals (Saudi Arabia)

Text preceding or following the note

1994

Text of Note

The Steiner Tree Problem is the determination of the shortest connecting length between a given set of points and additional points. The Rectilinear Steiner Tree Problem is the same as above but the connecting lines are confined to the horizontal or vertical lines only (usdL\sb1usd metric). A cluster is a set of points that "influence" each other locally. This research gives a new algorithm based on a clustering metric that determines much less steiner points locally in a cluster as well as those external to it. The algorithm matches the worst-case time complexity of O(nlogn) of previous authors while giving better average results then theirs. In addition, a Neural Solution to the Steiner problem in Networks, which is a graph-theoretic representation of the problem, is explored and its limitations presented.

Applied sciences

Computer science

Y. K. Karimjee

Electronic name

p

[Thesis]

276903

a

Y