Efficient algorithms for a mixed k-partition problem of graphs without specifying bases

This paper describes efficient algorithms for partitioning a k-edge-connected graph into k edge-disjoint connected subgraphs, each of which has a specified number of elements (vertices and edges). If each subgraph contains the specified element (called base), the authors call this problem the mixed k-partition problem with bases (called k-PART-WB), otherwise they call it the mixed k-partition problem without bases (called k-PART-WOB). In this paper, the authors show that k-PART-WB always has a solution for every k-edge connected grpah and they consider the problem without bases and the obtain the following results: (1) for any , k-PART-WOB can be solved in time for every 4-edge-connected graph G=(V, E) and (2) 3-PART-WOB can be solved in for every 2-edge-connected graph G=(V, E). [In Japanese.]