Return to search

Complexity and Approximation of the Rectilinear Steiner Tree Problem

Given a finite set K of terminals in the plane. A
rectilinear Steiner minimum tree for K (RST) is
a tree which interconnects among these terminals
using only horizontal and vertical lines of shortest
possible length containing Steiner point. We show the
complexity of RST i.e. belongs to NP-complete.
Moreover we present an approximative method of
determining the solution of RST problem proposed by Sanjeev Arora
in 1996, Arora's Approximation Scheme. This algorithm
has time complexity polynomial in the number of
terminals for a fixed performance ratio 1 + Epsilon.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:19169
Date21 July 2009
CreatorsMussafi, Noor Saif Muhammad
ContributorsTechnische Universität Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0017 seconds