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
  • 1
    Electronic Resource
    Electronic Resource
    On greedy heuristics for steiner minimum trees (1995)
    Springer
    Algorithmica 13 (1995), S. 381-386 
    Details
    ISSN: 1432-0541
    Keywords: Steiner trees ; Greed heuristic
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to√3/2. We also propose a new conjecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293486
    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 complexity of subset interconnection designs (1995)
    Springer
    Journal of global optimization 6 (1995), S. 193-205 
    Details
    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
    URL: http://dx.doi.org/10.1007/BF01096768
    Library Location Call Number Volume/Issue/Year 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...