EFFICIENT ALGORITHMS FOR SOME K-PARTITION PROBLEM OF GRAPHS

The k-element graph partition is as follows: given an input consisting of (1) a non-directed graph G = (V, E), (2) S subset of or equal to V boolean OR E, (3) k different points or edges a(i) (a(1), a(2),...,a( k) is an element of S) (all of the a(i) are called bases), and (4) k n atural numbers n(1), n(2),...,n(k) such that Sigma(i = 1)(k) n(i) = \S \, to find a solution such that each R-i in the partition R-1, R-2..., R-k of S contains a(i) and contains n(i) elements, and the connected p artial graphs G(i) (G(1), G(2),....,G(k)) that contain the R-i are mut ually edge-independent, The same problem with condition (3) removed is called the basis-unspecified k-element problem. In this paper we demo nstrate that a necessary and sufficient condition for the existence of a k-element; partition is that the input graph be k-edge-connected; v ie then show that it is efficiently solvable for the cases k = 2, 3, F or the basis-unspecified k-element problem we demonstrate that (1) if G is 2-edge-connected, then the base-unspecified 3-element problem is solvable in time O(\V\(2)); (2) if G is 4-edge-connected, then the k-e lement partition fork 2 3 is effectively solvable in time O(\V\root\V\ log \V\ + \E\). (C) 1997 Scripta Technica, Inc.