Abstract:
 1. Given a positive integer k and an undirected edgeweighted connected simple graph G with at least k edges of positive weight, we wish to partition the graph into k edgedisjoint connected components of approximately the same size. We focus on the maxmin ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the maxmin ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a lineartime algorithm for delivering a partition with maxmin ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible.
2. The content of this talk will be the main work of the Ph. D. dissertation of the speaker.
