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:bsz:ch1-200901213
Date05 August 2009
CreatorsMussafi, Noor Saif Muhammad
ContributorsTU Chemnitz, Fakultät für Mathematik
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:masterThesis
Formatapplication/pdf, text/plain, application/zip
RightsDokument ist für Print on Demand freigegeben

Page generated in 0.0021 seconds