Improved Steiner Tree Algorithms for Bounded Treewidth

Autor:	Petra Mutzel, Markus Chimani, Bernd Zey
Rok vydání:	2011
Předmět:	Vertex (graph theory) Discrete mathematics Steiner tree problem Polynomial algorithm Graph Combinatorics Treewidth symbols.namesake TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Bounded function symbols Algorithm Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642250101 IWOCA
DOI:	10.1007/978-3-642-25011-8_30
Popis:	We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in $\ensuremath{\mathcal{O}(B_{\ensuremath{\textit{tw}}+2}^2 \cdot \ensuremath{\textit{tw}}\ \cdot |V|)}$ time, where $\ensuremath{\textit{tw}}$ is the graph's treewidth and the Bell numberBk is the number of partitions of a k-element set. This is a linear time algorithm for graphs with fixed treewidth and a polynomial algorithm for $\ensuremath{\textit{tw}} = \ensuremath{\mathcal{O}(\log|V|/\log\log|V|)}$. While being faster than the previously known algorithms, our thereby used coloring scheme can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ed47ac29cb76bab26f3ad9bc7c2470f3 https://doi.org/10.1007/978-3-642-25011-8_30 Zobrazit plný text záznamu