Fiduccia-Mattheyses Partitioning

The idea

Three upgrades to Kernighan-Lin, each decisive. First, move single vertices instead of swapping pairs, with a balance constraint keeping the sides within tolerance; this halves the bookkeeping and lets sizes breathe. Second, netlists are hypergraphs (one net can connect many cells), and Fiduccia-Mattheyses computes gains on hyperedges correctly: a net contributes to the cut once, and only moves that empty a net's last cell from one side change its cut status. Third, the gain bucket: an array of doubly linked lists indexed by gain value, so selecting the best-gain movable vertex, moving it, and updating its neighbors' gains all run in amortized constant time. A full pass, every vertex moved once with the best-prefix rollback, costs time linear in total pin count.

Why it took over

Linear passes made iterated refinement affordable on real netlists, and the algorithm is straightforward to engineer: tie-breaking rules, balance tolerances, and multi-way extensions all slot in cleanly. Alone it is still a local method (quality degrades on huge graphs as single moves cannot see far), which is exactly the weakness multilevel partitioning repairs by running Fiduccia-Mattheyses at every coarsening level.

Where you meet it today

Inside effectively every serious partitioner (hMETIS and its relatives run Fiduccia-Mattheyses-style refinement at each level), inside min-cut placers like Capo, in clustering flows, and in any tool that says "FM refinement" in its documentation: that is this algorithm, forty years on.