dc.contributor.author | Pilipczuk, Marcin | |
dc.contributor.author | Pilipczuk, Michal Pawel | |
dc.contributor.author | van Leeuwen, Erik Jan | |
dc.contributor.author | Sankowski, Piotr | |
dc.date.accessioned | 2016-06-03T09:11:14Z | |
dc.date.available | 2016-06-03T09:11:14Z | |
dc.date.issued | 2013 | |
dc.Published | Leibniz International Proceedings in Informatics 2013, 20:353-364 | eng |
dc.identifier.isbn | 978-3-939897-50-7 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/1956/12056 | |
dc.description.abstract | The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus graphs, or, more generally, graphs with a fixed excluded minor. However, in order to apply the bidimensionality framework the considered problem needs to fulfill a special density property. Some well-known problems do not have this property, unfortunately, with probably the most prominent and important example being the Steiner Tree problem. Hence the question whether a subexponential-time parameterized algorithm for Steiner Tree on planar graphs exists has remained open. In this paper, we answer this question positively and develop an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph. Our algorithm does not rely on tools from bidimensionality theory or graph minors theory, apart from Baker's classical approach. Instead, we introduce new tools and concepts to the study of the parameterized complexity of problems on sparse graphs. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY-ND 3.0 | eng |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/3.0/ | eng |
dc.subject | Planar graphs | eng |
dc.subject | Steiner tree | eng |
dc.subject | subexponential-time algorithms | eng |
dc.title | Subexponential-time parameterized algorithm for Steiner tree on planar graphs | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2016-04-07T06:46:20Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.stacs.2013.353 | |
dc.identifier.cristin | 1069662 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 353-364 | |
dc.subject.nsi | VDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422 | |
dc.subject.nsi | VDP::Mathematics and natural scienses: 400::Information and communication science: 420::Algorithms and computability theory: 422 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2013, 20:353-364 | |
dc.source.volume | 20 | |