ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

A fast algorithm for Steiner trees (1981)

Kou, L. ; Markowsky, G. ; Berman, L.

Springer

Acta informatica 15 (1981), S. 141-145

add to mindlist on the mindlist

Details

ISSN: 1432-0525

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science

Notes: Summary Given an undirected distance graph G=(V, E, d) and a set S, where V is the set of vertices in G, E is the set of edges in G, d is a distance function which maps E into the set of nonnegative numbers and S⊑V is a subset of the vertices of V, the Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. In this paper, we analyze a heuristic algorithm for the Steiner tree problem. The heuristic algorithm has a worst case time complexity of O(¦S¦¦V¦ 2) on a random access computer and it guarantees to output a tree that spans S with total distance on its edges no more than 2(1−1/l) times that of the optimal tree, where l is the number of leaves in the optimal tree.

Type of Medium: Electronic Resource

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

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit