Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorFomin, Fedor V.
dc.contributor.authorKaski, Petteri
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.schoolSchool of Scienceen
dc.date.accessioned2016-10-20T09:01:28Z
dc.date.available2016-10-20T09:01:28Z
dc.date.issued2015
dc.description.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_40en
dc.description.versionPeer revieweden
dc.format.extent494-505
dc.format.mimetypeapplication/pdfen
dc.identifier.citationFomin, 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.en
dc.identifier.doi10.1007/978-3-662-47672-7_40
dc.identifier.isbn978-3-662-47672-7 (electronic)
dc.identifier.isbn978-3-662-47671-0 (printed)
dc.identifier.issn0302-9743 (electronic)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/23026
dc.identifier.urnURN:ISBN:978-3-662-47672-7
dc.language.isoenen
dc.publisherSpringer Science + Business Mediaen
dc.relationinfo:eu-repo/grantAgreement/EC/FP7/338077
dc.relation.ispartofAutomata, Languages, and Programming, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part Ien
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseries9134
dc.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.en
dc.rights.holderSpringer-Verlag Berlin Heidelberg
dc.subject.keywordSteiner treeen
dc.subject.keywordparameterized algorithmen
dc.subject.keywordpolynomial spaceen
dc.subject.otherComputer scienceen
dc.titleParameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Treeen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.dcmitypetexten
dc.type.versionPost printen

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
isbn9783662476727.pdf
Size:
558.53 KB
Format:
Adobe Portable Document Format
Download

Collections

[comp] Perustieteiden korkeakoulu / SCI