ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

Approximations for Steiner Trees with Minimum Number of Steiner Points (2000)

CHEN, DONGHUI ; DU, DING-ZHU ; HU, XIAO-DONG ; [weitere]

Springer

Journal of global optimization 18 (2000), S. 17-33

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1573-2916

Schlagwort(e): Steiner trees ; Approximation algorithms ; VLSI design ; WDM optical networks

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik

Notizen: Abstract Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1023/A:1008384012064

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer