On Rooted Node-Connectivity Problems
On Rooted Node-Connectivity Problems
复制标题
关于根节点连接问题
DOI：
10.1007/s00453-001-0017-7
复制
发表时间：
2001
期刊：
影响因子：
1.1
通讯作者：
Zeev Nutov
中科院分区：
文献类型：
--
作者：
J. Cheriyan;T. Jordán;Zeev Nutov
令GetGbe是一个从一个指定的根结点k-外连通的图，也就是说，对于每个结点，都有一个开路不交的图。我们给出了存在成对边的充要条件，用一条新的边代替这些边可以得到一个k-外连通的图。这推广了Bienstock等人的一个定理。在保持k-节点连通性的情况下，我们还证明了如果C是一个圈，使得C中的每条边对于r的k-out连通性来说是关键的，则C有一个节点v，它不同于有度的r。我们将上述结果应用于以下问题的近似算法设计：给定一个边权为非负且每个结点都有结点要求的图，找到一个最小权子图，它包含每对结点u之间的最大{cu，cv}条开不交路径，v.对于度量权，我们的近似保证是3.对于均匀加权，我们的逼近保证是\min{2，(k+2q-1)/k}。这里k是最大节点要求，q是正节点要求的个数。
LetGbe a graph which isk-outconnected from a specified root noder, that is,Ghaskopenly disjoint paths betweenrandvfor every nodev. We give necessary and sufficient conditions for the existence of a pairrv,rwof edges for which replacing these edges by a new edgevwgives a graph that isk-outconnected fromr. This generalizes a theorem of Bienstock et al. on splitting off edges while preservingk-node-connectivity.We also prove that ifCis a cycle inGsuch that each edge inCis critical with respect tok-outconnectivity fromr, thenChas a nodev, distinct fromr, which has degreek. This result is the rooted counterpart of a theorem due to Mader.We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge weights and node requirementscufor each nodeu, find a minimum-weight subgraph that contains max{cu,cv}openly disjoint paths between every pair of nodesu,v. For metric weights, our approximation guarantee is3. For uniform weights, our approximation guarantee is\min{ 2, (k+2q-1)/k}. Herekis the maximum node requirement, andqis the number of positive node requirements.