Fomin, Fedor V. ; Grandoni, Fabrizio ; Kratsch, Dieter ; Lokshtanov, Daniel ; Saurabh, Saket (2013) Computing Optimal Steiner Trees in Polynomial Space Algorithmica, 65 (3). pp. 584-604. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s00453-012-9612-z
Related URL: http://dx.doi.org/10.1007/s00453-012-9612-z
Abstract
Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62n)-time enumeration are based on dynamic programming, and require exponential space.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123444 |
| Deposited On: | 16 Sep 2021 12:02 |
| Last Modified: | 16 Sep 2021 12:02 |
Repository Staff Only: item control page
