We use cookies to improve your experience with our site.
Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
Citation:
Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
Citation:
Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph
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|.
DownLoad: