EFFICIENT ALGORITHMS FOR A MIXED K-PARTITION PROBLEM OF GRAPHS WITHOUT SPECIFYING BASES

This paper describes efficient algorithms for partitioning a k-edge-co nnected graph into k edge-disjoint connected subgraphs, each of which has a specified number of elements (vertices and edges). If each subgr aph contains the specified element (called base), we call this problem the mixed k-partition problem with bases (called k-PART-WB), otherwis e we call it the mixed k-partition problem without bases (called k-PAR T-WOB). In this paper, we show that k-PART-WB always has a solution fo r every k-edge-connected graph and we consider the problem without bas es and we obtain the following results: (1) for any k greater than or equal to 2, k-PART-WOB can be solved in O(/V/ root/V/log(2)/V/ + /E/) time for every 4-edge-connected graph G = (V,E), (2) 3-PART-WOB can be solved in O(/V/(2)) for every 2-edge-connected graph G =(V,E) and (3) 4-PART-WOB can be solved in O(/E/(2)) for every 3-edge-connected grap h G = (V,E). (C) 1998 - Elsevier Science B.V. All rights reserved.