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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-200901213 |
| Date | 05 August 2009 |
| Creators | Mussafi, Noor Saif Muhammad |
| Contributors | TU Chemnitz, Fakultät für Mathematik |
| Publisher | Universitätsbibliothek Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:masterThesis |
| Format | application/pdf, text/plain, application/zip |
| Rights | Dokument ist für Print on Demand freigegeben |
Page generated in 0.0021 seconds