A class of bounded approximation algorithms for graph partitioning

Abstract

Abstract This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.