Improved Steiner Tree Algorithms for Bounded Treewidth
Improved Steiner Tree Algorithms for Bounded Treewidth
复制标题
DOI：
10.1007/978-3-642-25011-8_30
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Markus Chimani;Petra Mutzel;Bernd Zey
中科院分区：
文献类型：
--
作者：
Markus Chimani;Petra Mutzel;Bernd Zey
本文提出了一种新的算法来解决具有最优点集V的图的Steiner树问题，其中图的树宽，Bell数Bk是AK-元素集的划分数。这是一个用于固定树宽图的线性时间算法和一个用于的多项式算法。在比已知的算法更快的同时，我们由此使用的着色方案可以被扩展以给出用于获奖的Steiner树以及Thek-基数树问题的新的改进算法。
We propose a new algorithm that solves the Steiner tree problem on graphs with vertex setVto optimality intime, whereis the graph’s treewidth and theBell numberBkis the number of partitions of ak-element set. This is a linear time algorithm for graphs with fixed treewidth and a polynomial algorithm for.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 thek-cardinality tree problems.