Parameterized Algorithms for Stochastic Steiner Tree Problems
Parameterized Algorithms for Stochastic Steiner Tree Problems
复制标题
随机斯坦纳树问题的参数化算法
DOI：
10.1007/978-3-642-36046-6_14
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
B. Zev
中科院分区：
文献类型：
--
作者：
D. Kurz;P. Mutzel;B. Zev
我们考虑不确定性下图中的Steiner树问题，即所谓的两阶段随机Steiner树问题（SSTP）。这个问题包括两个阶段：在第一阶段，我们不知道哪些节点需要连接。相反，我们知道我们可能购买边缘的成本，以及一组可能的场景，其中一个场景将在第二阶段出现。每个场景都由自己的终端集、概率和第二阶段边成本组成。我们希望为每个场景找到第一阶段边缘和第二阶段边缘的选择，以最大限度地减少预期成本并满足所有连接要求。我们表明，SSTP是在固定参数易处理的问题（FPT），参数化终端的数量。此外，我们将我们的结果转移到SSTP的定向和奖品收集变体。
We consider the Steiner tree problem in graphs under uncertainty, the so-called two-stage stochastic Steiner tree problem (SSTP). The problem consists of two stages: In the first stage, we do not know which nodes need to be connected. Instead, we know costs at which we may buy edges, and a set of possible scenarios one of which will arise in the second stage. Each scenario consists of its own terminal set, a probability, and second-stage edge costs. We want to find a selection of first-stage edges and second-stage edges for each scenario that minimizes the expected costs and satisfies all connectivity requirements. We show that SSTP is in the class of fixed-parameter tractable problems (FPT), parameterized by the number of terminals. Additionally, we transfer our results to the directed and the prize-collecting variant of SSTP.
登录
查看更多内容
DOI：
10.1007/978-3-642-25011-8_30
发表时间：
2011-07
期刊：
--
影响因子：
--
作者：
Markus Chimani;Petra Mutzel;Bernd Zey
通讯作者：
Markus Chimani;Petra Mutzel;Bernd Zey
高阶模型检验的平均情况硬度
DOI：
--
发表时间：
2020
期刊：
5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)
影响因子：
--
作者：
Yoshiki Nakamura;Kazuyuki Asada;Naoki Kobayashi;Ryoma Sin'ya;Takeshi Tsukada
通讯作者：
Takeshi Tsukada
用两阶段分支割法求解两阶段随机 Steiner 树问题
DOI：
10.1007/978-3-642-17517-6_38
发表时间：
2010
期刊：
SIAM J. Comput.
影响因子：
--
作者：
I. Bomze;Markus Chimani;M. Jünger;I. Ljubić;Petra Mutzel;Bernd Zey
通讯作者：
Bernd Zey
影响因子：
2.7
作者：
Anupam Gupta;Martin Pál
通讯作者：
Martin Pál
影响因子：
--
作者：
PRIM, RC
通讯作者：
PRIM, RC