|
|||||
|
|
| K-vertex-connectivity minimum augmentation for undirected unweighted graphs | |
| 引用本文： | CAO Qiguo,WU Xue,SUN Yugeng. K-vertex-connectivity minimum augmentation for undirected unweighted graphs[J]. 自然科学进展(英文版), 2003, 13(6): 434-445 |
| 作者姓名： | CAO Qiguo WU Xue SUN Yugeng |
| 作者单位： | School of Electrical Automation and Energy Engineering, Tianjin University, Tianjin 300072, China,School of Electrical Automation and Energy Engineering, Tianjin University, Tianjin 300072, China,School of Electrical Automation and Energy Engineering, Tianjin University, Tianjin 300072, China |
| 基金项目： | Supported by the Education Ministry Doctoral Discipline Foundation of China (Grant No. 2000005634) |
| 摘 要： | For an undirected unweighted graph G0＝(V0,E0) and a positive integer K, the K-vertex-connectivity minimum augmentation problem (K-VCMAP) is to find a minimum set of edges Emin such that the graph H0＝(V0,E0∪Emin) is K-vertex-connected. Results in the literature have given polynomial time algorithms for K-VCMAP in several special cases such as where k≤3, or G0 is a tree. However, it still remains open whether or not there exist polynomial time algorithms for K-VCMAP for any graph G0 and any integer K. In this paper, we settle the problem by describing an efficient algorithm (KUCA) with time-complexity of O(K|V(G0)|5) for the K-VCMAP for any G0 and any positive integer K. |
| 关 键 词： | K-vertex-connectivity minimum extended augmentation admissible lifting KR-arc-connected graphs f |
K-vertex-connectivity minimum augmentation for undirected unweighted graphs |
|
| CAO Qiguo,WU Xue,Sun Yugeng. K-vertex-connectivity minimum augmentation for undirected unweighted graphs[J]. Progress in Natural Science, 2003, 13(6): 434-445 | |
| Authors: | CAO Qiguo WU Xue Sun Yugeng |
| Affiliation: | School of Electrical Automation and Energy Engineering, Tianjin University, Tianjin 300072, China |
| Abstract: | For an undirected unweighted graph G0＝(V0,E0) and a positive integer K, the K-vertex-connectivity minimum augmentation problem (K-VCMAP) is to find a minimum set of edges Emin such that the graph H0＝(V0,E0∪Emin) is K-vertex-connected. Results in the literature have given polynomial time algorithms for K-VCMAP in several special cases such as where k≤3, or G0 is a tree. However, it still remains open whether or not there exist polynomial time algorithms for K-VCMAP for any graph G0 and any integer K. In this paper, we settle the problem by describing an efficient algorithm (KUCA) with time-complexity of O(K|V(G0)|5) for the K-VCMAP for any G0 and any positive integer K. |
| Keywords: | K-vertex-connectivity minimum extended augmentation admissible lifting KR-arc-connected graphs f |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 | |
| 点击此处可从《自然科学进展(英文版)》下载全文 | |