Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
Loading...
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.
Date
2015
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
Keywords
Steiner tree, parameterized algorithm, polynomial space
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.
