Algorithms for node‐weighted Steiner tree and maximum‐weight connected subgraph Academic Article uri icon

abstract

  • © 2018 Wiley Periodicals, Inc. 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 O(n3) for n-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 O(1.5296n) 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 O(1.5875n). To the best of the authors’ knowledge, these are the first improvements over exhaustive search in the literature.

altmetric score

  • 1

author list (cited authors)

  • Buchanan, A., Wang, Y., & Butenko, S.

citation count

  • 4

publication date

  • April 2018

publisher