A computational study of graph partitioning (Q1340061)

For a graph with weights on edges, the graph partitioning problem is the problem of partitioning the node set into \(k\) disjoint subsets of specified size so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. This paper provides a numerical way on the use of an eigenvalue-based technique to find upper and lower bounds for the problem. Results for the case \(k= 2\) with up to thousand nodes are given, and for small graphs some results of the case \(k= 3\) are also presented.