Fomin, Fedor V. ; Kaski, Petteri ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket (2015) Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree Lecture Notes in Computer Science, 9134 . pp. 494-505. ISSN 0302-9743
Full text not available from this repository.
Official URL: http://doi.org/10.1007/978-3-662-47672-7_40
Related URL: http://dx.doi.org/10.1007/978-3-662-47672-7_40
Abstract
In the Steiner tree problem, we are given as input a connected n -vertex graph with edge weights in {1,2,…,W} , and a subset of k terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time O(7.97k⋅n4⋅logW) using O(n3⋅lognW⋅logk) space. This is the first single-exponential time, polynomial-space FPT algorithm for the weighted Steiner Tree problem.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123373 |
| Deposited On: | 15 Sep 2021 10:47 |
| Last Modified: | 15 Sep 2021 10:47 |
Repository Staff Only: item control page
