Article ID Journal Published Year Pages File Type
1143265 Operations Research Letters 2006 9 Pages PDF
Abstract

We show that the Kernighan–Lin like linear time heuristic for bipartitioning unweighted graphs by Fiduccia and Mattheyses can be generalized to kk-partitioning with the same time bounds, avoiding the logarithmic increase incurred by recursive bipartitioning. Furthermore, the direct heuristic allows a better control of the cut.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Direct graph kk-partitioning with a Kernighan–Lin like heuristic
Authors
,