Library

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
  • 1990-1994  (9)
  • 1
    Electronic Resource
    Electronic Resource
    Minimum steiner trees in normed planes (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 351-370 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the “unit disk” is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratioρ(D) forD, and show that, for anyD, 0.623〈ρ(D)〈0.8686.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189328
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Book reviews (1993)
    Springer
    Journal of global optimization 3 (1993), S. 257-259 
    Details
    ISSN: 1573-2916
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096743
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A continuous version of a result of Du and Hwang (1994)
    Springer
    Journal of global optimization 5 (1994), S. 127-129 
    Details
    ISSN: 1573-2916
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In the proof of Gilbert-Pollak conjecture on the Steiner ratio, a result of Du and Hwang on a minimax problem played an important role. In this note, we prove a continuous version of this result.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01100689
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On steiner ratio conjectures (1991)
    Springer
    Annals of operations research 33 (1991), S. 437-449 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract LetM be a metric space andP a finite set of points inM. The Steiner ratio inM is defined to beρ(M)=inf{L s(P)/L m(P) |P ⊂M}, whereL s(P) andL m(P) are the lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. In this paper, we study various conjectures onρ(M). In particular, we show that forn-dimensional Euclidean spaceℝ n ,ρ(ℝ n )〉0.615.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02071981
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Book review (1994)
    Springer
    Journal of global optimization 5 (1994), S. 405-406 
    Details
    ISSN: 1573-2916
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096690
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Book
    Book
    Advances in optimization and approximation; 1 (1994)
    Dordrecht, Netherlands :Kluwer,
    Details
    Title: Advances in optimization and approximation; 1
    Contributer: Du, Ding-Zhu , Sun, Jie
    Publisher: Dordrecht, Netherlands :Kluwer,
    Year of publication: 1994
    Pages: 389 S.
    Series Statement: Nonconvex optimization & its applications 1
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 9
    Book
    Book
    Network optimization problems: algorithms, applications and complexity; Vol. 2 (1993)
    London u.a. :World Scientific,
    Details
    Title: Network optimization problems: algorithms, applications and complexity; Vol. 2
    Contributer: Du, Ding-Zhu , Pardalos, Panos M.
    Publisher: London u.a. :World Scientific,
    Year of publication: 1993
    Pages: 401 S.
    Series Statement: Series on applied mathematics Vol. 2
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...