Graph Augmentation Problems for a Specified Set of Vertices
Graph Augmentation Problems for a Specified Set of Vertices
复制标题
指定顶点集的图增广问题
DOI：
10.1007/3-540-52921-7_87
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
A. Nakamura
中科院分区：
文献类型：
--
作者：
Toshimasa Watanabe;Y. Higashi;A. Nakamura
论文讨论了指定顶点集的 k 边连通性或 k 顶点连通性或强连通性增强问题：“给定一个完整的无向或有向图 G=(V, E)、一个生成子图 G 0=(V, E')、一个成本函数 c: E-、Z+(非负整数) 和一个指定的子集 So_V，找到一个具有最小总成本 c (A) 的集合 Ac-EE'，使得对于任何给定的对S 中的顶点数，图 G0=(V, E'wA) 在它们之间至少有 k 个边不相交或至少 k 个内部不相交路径，或至少一个包含它们的有向环，其中 c (e)= 0 (Ve~ E') 并且禁止向图中添加多条边。它们分别缩写为 k-ECA-SV、k-VCA-SV 和 SCA-SV。如果我们设置 S= V，那么这些问题就是[1,2,4-8]中讨论的常见增强问题。在本文中，我们考虑最基本的问题 2-ECASV 和 2-VCA-SV，即 k= 2 的情况。这些 GO 限制为树且 S= V 的问题的 NP 完备性已在[2]中示出。文献[2]分别提出了SCA-SV、2-ECA-SV 和2-VCA-SV 的三种O (IVt 2) 近似算法STC、BRC 和BIC，且S=V。 STC的思想如下：首先选择一个顶点r，相对于初始成本c，找到一个以sink r跨越反向树状Tin的最小成本。通过设置 c'< u, v>= 0（对于 V< u, v>~ E (Tin)）和 c'< w, v>=~ （对于进入 r 的任何 < w, r>），将 c 修改为 c'。再次找到以 r 为根、相对于 c' 的最小成本跨越树状结构 Tout。显然，E"=(E (Tin) wE (Tout))-E' 是 SCA-SV 的解，其中 S= V。STC 的时间复杂度为 O (IVI2)，并且 c (E") 不超过最佳值的两倍。 BRC 和 BIC 中都使用了结合 Tin 和 Tou t 的想法，因为如果忽略有向性，强连通图将是 2 边连通的，其中割点的处理被合并到 BIC 中。我们提出了针对 2-ECA-SV 的 O (tVl 2) 近似算法 BRA-SV，以及针对 2-VCA-SV 的 O (IV31) 1 BIA-SV。结果表明，
The paper discusses the k-edge-connectivity or k-vertexconnectivity or strong-connectivity augmentation problem for a specified set of vertices:" Given a complete undirected or directed graph G=(V, E), a spanning subgraph G 0=(V, E'), a cost function c: E-, Z+(nonnegative integers) and a specified subset So_V, find a set Ac-EE'of the minimum total cost c (A) such that, for any given pair of vertices in S, the graph G0=(V, E'wA) has at least k edge-disjoint or at least k internally-disjoint paths between them or at least one directed cycle containing them, where c (e)= 0 (Ve~ E') and adding multiple edges to a graph is prohibited." They are abbreviated as k-ECA-SV, k-VCA-SV and SCA-SV, respectively, If we set S= V then these problems are usual augmentation problems discussed in [1, 2, 4-8]. In this paper we consider the most fundamental problems 2-ECASV and 2-VCA-SV, that is, the case with k= 2. The NP-completeness of these problems with GO restricted to a tree and S= V have been shown in [2]. Three O (IVt 2) approximation algorithms STC, BRC and BIC for SCA-SV, 2-ECA-SV and 2-VCA-SV, all with S= V, were proposed in [2], respectively. The idea of STC is as follows: First choose a vertex r and finds a minimum cost spanning reverse arborescence Tin with the sink r, with respect to the initial cost c. Modify c into c'by setting c'< u, v>= 0 for V< u, v>~ E (Tin) and c'< w, v>=~ for any< w, r> entering into r. Again finds a minimum cost spanning arborescence Tou t with r as the root, with respect to c'. Clearly E"=(E (Tin) wE (Tout))-E'is a solution to SCA-SV with S= V. Time complexity of STC is O (IVI2), and c (E") is no more than twice the optimal. The idea of combining Tin and Tou t is used in both BRC and BIC, since a strongly connected graph will be 2-edge-connected if directedness is neglected, where the handling of cutvertices are incorporated in BIC. We propose an O (tVl 2) approximation algorithm BRA-SV for 2-ECA-SV, and an O (IV31) one BIA-SV for 2-VCA-SV. It is shown that the