ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

On Steiner minimal trees withL p distance (1992)

Liu, Zi -Cheng ; Du, Ding -Zhu

Springer

Algorithmica 7 (1992), S. 179-191

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1432-0541

Schlagwort(e): Steiner trees ; Spanning trees ; Steiner ratio ; L p distance ; Bounds

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik , Mathematik

Notizen: Abstract LetL p be the plane with the distanced p (A 1 ,A 2 ) = (¦x 1 −x 2¦ p + ¦y1 −y 2¦p)/1p wherex i andy i are the cartesian coordinates of the pointA i . LetP be a finite set of points inL p . We consider Steiner minimal trees onP. It is proved that, for 1 〈p 〈 ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ϱ p to be inf{L s (P)/L m (P)¦P⊂L p } whereL s (P) andL m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ϱ1 = 2/3. Chung and Graham proved ϱ2 〉 0.842. We prove in this paper that ϱ{∞} = 2/3 and √(√2/2)ϱ1ϱ2 ≤ ϱp ≤ √3/2 for anyp.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01758757

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer