论文标题
$ 2 $ - 节点连接性网络设计
$2$-node-connectivity network design
论文作者
论文摘要
我们考虑了为我们提供图形的网络设计问题，并寻求满足规定属性的最小尺寸$ 2 $连接的子图。 $ \ bullet $在1-连接性增强问题中的目标是通过指定边缘集的最小边缘子集增强连接的图形，以使增强图为$ 2 $连接。对于此问题，我们违反了$ 2 $的自然比率以及更普遍的Crossing家庭封面问题。 $ \ bullet $在$ 2 $连接的主体设置问题中，我们寻求最低尺寸$ 2 $连接的子图，该子图将主导所有节点。我们给出了此问题的第一个非平地近似算法，预期比率$ o（σ\ log^3 n）$，其中$σ= o（\ log n \ cdot \ cdot \ log \ log \ log n \ cdot（\ log log \ log \ log \ log \ log \ log \ log \ log n）^{3}）$。 这两种结果的统一技术是将steiner Connected主导的集合问题减少。这种减少的边缘连接性已知，我们将其扩展到$ 2 $节点的连接问题。我们表明，可以使用相同的方法来获取易于与其他几个问题的最著名的近似值率易于近距离。
We consider network design problems in which we are given a graph and seek a min-size $2$-connected subgraph that satisfies a prescribed property. $\bullet$ In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a min-size edge subset of a specified edge set such that the augmented graph is $2$-connected. We breach the natural ratio of $2$ for this problem and also for the more general Crossing Family Cover problem. $\bullet$ In the $2$-Connected Dominating Set problem we seek a minimum size $2$-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm for this problem, with expected ratio $O(σ\log^3 n)$, where $σ=O(\log n \cdot\log\log n\cdot(\log\log\log n)^{3})$. The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to $2$-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.
