A linear time algorithm for minimum augmentation to 3-connect specified vertices of a graph
A linear time algorithm for minimum augmentation to 3-connect specified vertices of a graph
复制标题
用于最小增强图的 3 连接指定顶点的线性时间算法
DOI：
10.1109/iscas.1997.621905
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
T. Watanabe
中科院分区：
文献类型：
--
作者：
T. Mashima;T. Watanabe
本文的主题是一个指定顶点集的3-顶点连通性扩充问题（3VCA-SV），它的定义如下：给定一个无向图G=（V，E）和V的一个指定子集S，|S|>3，找到要添加到G的最小边集，使得所得到的图可以具有这样的性质：即使从其中删除任何两个顶点，在S中的任何剩余顶点对之间也存在路径。本文的结果是3VCA-SV可以在线性时间内得到最优解。
The subject of the paper is the 3-vertex-connectivity augmentation problem for a specified set of vertices (3VCA-SV), which is defined as follows: given an undirected graph G=(V, E) and a specified subset S of V with |S|>3, find a smallest set of edges to be added to G so that the resulting graph may have the property that, even after deleting any two vertices from it, there is a path between any pair of remaining vertices in S. The result of the paper is that 3VCA-SV can be solved optimally in linear time.