Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
复制标题
节点加权斯坦纳树和最大权连通子图的算法
DOI：
10.1002/net.21825
复制
发表时间：
2018
期刊：
影响因子：
2.1
通讯作者：
Butenko, Sergiy
中科院分区：
文献类型：
--
作者：
Buchanan, Austin;Wang, Yiming;Butenko, Sergiy
本文考虑节点加权Steiner树（NWST）问题和最大权连通子图（MWCS）问题，它们在电信网络设计和生物网络分析中有应用。提供了具有可证明的最坏情况运行时的精确算法。第一个算法的NWST运行在时间为n-顶点实例时，终端的数量是有界的。它基于动态规划，推广了Dreyfus和瓦格纳的Steiner树算法。当与Hakimi的生成树枚举算法一起使用时，它意味着NWST的时间算法。它还表明，哈基米的46岁的算法施泰纳树基本上是最好的可能下的强指数时间假设（SETH）。在此基础上，提出了两种MWCS算法。它们的运行时间在图的顶点数量上是多项式的，但在具有正（或负）权重的顶点数量上是指数的。后者在SETH下基本上是最好的。总之，它们意味着MWCS可以及时解决。据作者所知，这些是对文献中穷举搜索的第一次改进。
This article considers the node‐weighted Steiner tree (NWST) problem and the maximum‐weight connected subgraph (MWCS) problem, which have applications in the design of telecommunication networks and the analysis of biological networks. Exact algorithms with provable worst‐case runtimes are provided. The first algorithm for NWST runs in time forn‐vertex instances when the number of terminals is bounded. It is based on dynamic programming and generalizes a Steiner tree algorithm of Dreyfus and Wagner. When used alongside Hakimi's spanning tree enumeration algorithm, it implies a time algorithm for NWST. It is also shown that Hakimi's 46‐year‐old algorithm for Steiner tree is essentially best‐possible under the strong exponential time hypothesis (SETH). Then two algorithms for MWCS are provided. Their runtimes are polynomial in the number of vertices of the graph, but exponential in the number of vertices that have positive (or negative) weight. The latter is shown to be essentially best‐possible under SETH. Together, they imply that MWCS can be solved in time . To the best of the authors’ knowledge, these are the first improvements over exhaustive search in the literature.