1
$\begingroup$

I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions.

Is there some technique to combine gain functions in one algorithm?

The KL algorithm and its gain function is defined here for example:

http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2

$\endgroup$
  • 1
    $\begingroup$ Could you please provide some motivation and explain why you are interested in this question? $\endgroup$ – Kaveh Nov 23 '10 at 17:13
  • 2
    $\begingroup$ My guess would be that the OP wants to use the Kernighan-Lin algorithm to do multi-criterion optimization. $\endgroup$ – Peter Shor Nov 24 '10 at 1:37
5
$\begingroup$

Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.

Kim, Moon, Lock-gain based Graph Partitioning, J Heuristics, 10, 37-57, 2004.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.