A projection technique for partitioning the nodes of a graph

• DOI: 10.1007/bf02032130
• Publication Date: 2005-08-10T15:19:28Z
• Authors: Franz Rendl; Henry Wolkowicz
• Keywords: 0102 computer and information sciences; 01 natural sciences

LetG=(N,E) be an undirected graph. We present several new techniques for partitioning the node setN intok disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful.