 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources3
 Resource Type

30
 Availability

21
 Author / Contributor
 Filter by Author / Creator


Kobourov, S. (3)

Wolff, A. (3)

Ahmed, R. (1)

Angelini, P. (1)

Efrat, A. (1)

Frank, F. (1)

Glickenstein, D. (1)

Goessmann, I. (1)

Gronemann, M. (1)

Heinsohn, N. (1)

Kaufmann, M. (1)

Klawitter, J. (1)

Klemz, B. (1)

Klesen, F. (1)

Kryven, M. (1)

Mchedlidze, T. (1)

Pupyrev, S. (1)

Sahneh, F. (1)

Spence, R. (1)

Ueckerdt, T. (1)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Higgins, A. (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Agarwal (0)

A. Beygelzimer (0)

A. E. Lischka (0)

A. E. Lischka, E. B. (0)

A. E. Lischka, E.B. Dyer (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available October 1, 2023

Frank, F. ; Kaufmann, M. ; Kobourov, S. ; Mchedlidze, T. ; Pupyrev, S. ; Ueckerdt, T. ; Wolff, A. ( , 47th Intl. Conference on Current Trends in Theory and Practice of Computer Science (SofSem))

Ahmed, R. ; Angelini, P. ; Sahneh, F. ; Efrat, A. ; Glickenstein, D. ; Gronemann, M. ; Heinsohn, N. ; Kobourov, S. ; Spence, R. ; Watkins, J. ; et al ( , Symposium on Experimental Algorithms)In the classical Steiner tree problem, given an undirected, connected graph G=(V,E) with nonnegative edge costs and a set of terminals T⊆V, the objective is to find a minimumcost tree E′⊆E that spans the terminals. The problem is APXhard; the best known approximation algorithm has a ratio of ρ=ln(4)+ε<1.39. In this paper, we study a natural generalization, the multilevel Steiner tree (MLST) problem: given a nested sequence of terminals Tℓ⊂⋯⊂T1⊆V, compute nested trees Eℓ⊆⋯⊆E1⊆E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multilevel Network Design, QualityofService Multicast tree, GradeofService Steiner tree, and MultiTier tree. Several approximation results are known. We first present two simple O(ℓ)approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most 2ℓ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running timesmore »on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to ℓ=100 levels, which is sufficient for most applications such as network visualization or designing multilevel infrastructure.« less