论文标题
2个连接网络设计的算法和具有恒定端子数量的灵活的坦源树
Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
论文作者
论文摘要
$ k $ -steiner-2ncs问题如下：给定$ k $，以及$ e $上的无向连接图$ g =（v，e）$，$ e $上的非负费用$ c $，以及一套terminals，$ t $ y of term $ t $的分区$（t，v-t，v-t，v，v-t）$ v $ |最小成本两节点连接的子图包含终端。 我们为未加权问题提供了一种随机多项式算法，以及加权问题的随机PTA。 我们获得了$ K $ -Steiner-2EC问题的相似结果，其中输入是相同的，并且算法目标是找到一个包含终端的最低成本的两边连接子图。 我们的方法基于Björklund，Husfeldt和Taslaman（ACM-Siam Soda 2012）的结果，这些方法为未加权的$ K $ - steiner-Cycle问题提供了随机的多项式时间算法；这个问题的输入与未加权的$ K $ -STEINER-2NCS问题相同，算法目标是找到一个包含终端的最小尺寸的简单循环$ C $（$ c $可能包含任何数量的steiner节点）。
The $k$-Steiner-2NCS problem is as follows: Given a constant $k$, and an undirected connected graph $G = (V,E)$, non-negative costs $c$ on $E$, and a partition $(T, V-T)$ of $V$ into a set of terminals, $T$, and a set of non-terminals (or, Steiner nodes), where $|T|=k$, find a minimum-cost two-node connected subgraph that contains the terminals. We present a randomized polynomial-time algorithm for the unweighted problem, and a randomized PTAS for the weighted problem. We obtain similar results for the $k$-Steiner-2ECS problem, where the input is the same, and the algorithmic goal is to find a minimum-cost two-edge connected subgraph that contains the terminals. Our methods build on results by Björklund, Husfeldt, and Taslaman (ACM-SIAM SODA 2012) that give a randomized polynomial-time algorithm for the unweighted $k$-Steiner-cycle problem; this problem has the same inputs as the unweighted $k$-Steiner-2NCS problem, and the algorithmic goal is to find a minimum-size simple cycle $C$ that contains the terminals ($C$ may contain any number of Steiner nodes).
