ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Steiner trees  (3)
  • Springer  (3)
  • American Chemical Society
  • 1990-1994  (3)
  • 1
    Electronic Resource
    Electronic Resource
    On better heuristics for Steiner minimum trees (1992)
    Springer
    Mathematical programming 57 (1992), S. 193-202 
    Details
    ISSN: 1436-4646
    Keywords: Steiner trees ; approximation performance ratio
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than $${\textstyle{1 \over 2}}\sqrt 3 $$ . This solves a long-standing open problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581080
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A proof of the Gilbert-Pollak conjecture on the Steiner ratio (1992)
    Springer
    Algorithmica 7 (1992), S. 121-135 
    Details
    ISSN: 1432-0541
    Keywords: Steiner trees ; Spanning trees ; Steiner ratio ; Convexity ; Hexagonal trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a set ofn points on the euclidean plane. LetL s(P) andL m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L s (P)≥(√3/2)L m (P). We provide a proof for their conjecture in this paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758755
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On Steiner minimal trees withL p distance (1992)
    Springer
    Algorithmica 7 (1992), S. 179-191 
    Details
    ISSN: 1432-0541
    Keywords: Steiner trees ; Spanning trees ; Steiner ratio ; L p distance ; Bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758757
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...