Direct graph k-partitioning with a Kernighan–Lin like heuristic

Direct graph k-partitioning with a Kernighan–Lin like heuristic

0.00 Avg rating—0 Votes
Article ID: iaor20073054
Country: Netherlands
Volume: 34
Issue: 6
Start Page Number: 621
End Page Number: 629
Publication Date: Nov 2006
Journal: Operations Research Letters
Authors:
Keywords: heuristics
Abstract:

We show that the Kernighan–Lin like linear time heuristic for bipartitioning unweighted graphs by Fiduccia and Mattheyses can be generalized to k-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.

Reviews

Required fields are marked *. Your email address will not be published.