Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
Loading...
Access rights
© 2015 Springer-Verlag Berlin Heidelberg. This is the post print version of the following article: Fomin, Fedor V. & Kaski, Petteri & Lokshtanov, Daniel & Panolan, Fahad & Saurabh, Saket. 2015. Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. Automata, Languages, and Programming, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. Lecture Notes in Computer Science. 9134. 494-505. ISSN 0302-9743 (electronic). ISBN 978-3-662-47672-7 (electronic). ISBN 978-3-662-47671-0 (printed). DOI: 10.1007/978-3-662-47672-7_40, which has been published in final form at http://link.springer.com/chapter/10.1007/978-3-662-47672-7_40.
Post print
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
A4 Artikkeli konferenssijulkaisussa
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Fomin, Fedor V.
Kaski, Petteri
Lokshtanov, Daniel
Panolan, Fahad
Saurabh, Saket
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
494-505
Series
Lecture Notes in Computer Science, 9134
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.97^k n^4 log W) using O(n^3 log nW log k) space. This is the first single-exponential time, polynomial-space FPT algorithm for the weighted Steiner tree problem." PLEASE NOTE:This is an author-created version that the author has self-archived to the "Aaltodoc" (aaltodoc.aalto.fi) faculty-level repository at Aalto University. The final publication is available at link.springer.com via the link http://dx.doi.org/10.1007/978-3-662-47672-7_40Description
Other note
Citation
Fomin, Fedor V. & Kaski, Petteri & Lokshtanov, Daniel & Panolan, Fahad & Saurabh, Saket. 2015. Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. Automata, Languages, and Programming, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. Lecture Notes in Computer Science. 9134. 494-505. ISSN 0302-9743 (electronic). ISBN 978-3-662-47672-7 (electronic). ISBN 978-3-662-47671-0 (printed). DOI: 10.1007/978-3-662-47672-7_40.