Library

feed icon rss

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 7 (1992), S. 179-191 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Journal of global optimization 6 (1995), S. 193-205 
    ISSN: 1573-2916
    Keywords: Subset interconnection design ; globally optimal ; polynomial time
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Given a setX and subsetsX 1,...,X m, we consider the problem of finding a graphG with vertex setX and the minimum number of edges such that fori=1,...,m, the subgraphG i; induced byX i is connected. Suppose that for anyα pointsx 1,...,x α ε X, there are at mostβX i 's containing the set {x1,...,x α}. In the paper, we show that the problem is polynomial-time solvable for (α ⩽ 2,β ⩽ 2) and is NP-hard for (α⩾3,β=1), (α=l,β⩾6), and (α⩾2,β⩾3).
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...