Kernighan–Lin algorithm とは

この記事では、グラフ分割問題の発見的アルゴリズムについて説明します。走行営業員の問題に対するヒューリスティックについては、Lin-Kernighanヒューリスティックを参照してください。
Kernighan-Linアルゴリズムは、グラフのパーティションを見つけるヒューリスティックなアルゴリズムです。このアルゴリズムは、VLSIにおけるデジタル回路および構成要素のレイアウトにおいて重要な用途を有する。