Introduction
The Kernighan-Lin Algorithm is an algorithm I touched through school work. There are many algorithms I learned through classes. I believe they will be useful for the future. Since I spent time to understand them, I think it is worth to spent sometime to collect and organize them here. It will be easy for me to review them later.
Problem For This Algorithm
There is an edge-weighted undirected graph G(V,E); the graph has 2n vertices(V=2n); an edge(a,b) has weight Rab. The goal is to minimize the total weight of the edges cut by the partitioning of V into the sets A and B.
The Principle
The algorithm is starting with an initial partitial consisting of the sets A0 and B0. In an iterative process, subsets of both sets are isolated and interchanged. The iteration goes on until no improvement in the cut cost is possible.
If you have any questions, please contact with tianluwu@gmail.com