| An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph |
| |
| 引用本文： | Ma Jun,Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. 计算机科学技术学报, 1994, 9(1): 86-91. DOI: 10.1007/BF02939489 |
| |
| 作者姓名： | Ma Jun Ma Shaohan |
| |
| 作者单位： | [1]DepartmentofComputerScience,ShandongUniversity,Jinan250100 [2]DepartmentofComputerScience,ShandongUniver |
| |
| 摘 要： | Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively,there is no general algorithm of finding a k-partition for a k-connected graph G=(V,E),where k is the vertex connectivity of G.In this paper,an O(k^2n^2) general algorithm of finding a k-partition for a k-connected graph is proposed,where n=|V|.
|
| 关 键 词： | 图形算法 图形顶角连接 图形K－分段 |
AnO(k 2n2) algorithm to find ak-partition in ak-connected graph |
| |
| Jun Ma,Shaohan Ma. AnO(k 2n2) algorithm to find ak-partition in ak-connected graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91. DOI: 10.1007/BF02939489 |
| |
| Authors: | Jun Ma Shaohan Ma |
| |
| Affiliation: | Department of Computer Science; Shandong University; Jinan 250100; |
| |
| Abstract: | Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|. |
| |
| Keywords: | Graph algorithm graph vertex connectivity k-partition of a graph |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
