# Kernighan and Lin グラフ分割において、頂点対のswap(入れ替え)による局所探索でカットサイズを最適化するKernighan-Linアルゴリズムを提案した。同アルゴリズムはO(n^2 log n)で高速だが初期分割への依存が強く、単独で用いるより他手法が出した分割の後処理として使われることが多い(p.17-18)。