An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph
-
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|.
-
-