TRANSFORMATIONS FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM AND THE MAXIMUM-WEIGHT CONNECTED SUBGRAPH PROBLEM TO SAP

• 来源期刊: 计算数学（英文版）
• 关键词: Prize-collecting Steiner tree problem Maximum-weight connected subgraph problem Graph transformations Dual-ascent heuristics
• 年，卷（期）: 2018,（3）
• 页码范围: 459-468
• 页数: 10页
• 语种: 英文
• DOI: 10.4208/jcm.1709-m2017-0002

摘要

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.