Fiduccia–Mattheyses algorithm

A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Fiduccia and Mattheyses [Fiduccia 1982]. This heuristic is commonly called the FM algorithm.

Introduction

FM algorithm is a linear time heuristic for improving network partitions. New features to K-L heuristic:

• Aims at reducing net-cut costs; the concept of cutsize is extended to hypergraphs.
• Only a single vertex is moved across the cut in a single move.
• Vertices are weighted.
• Can handle "unbalanced" partitions; a balance factor is introduced.
• A special data structure is used to select vertices to be moved across the cut to improve running time.
• Time complexity O(P), where P is the total # of terminals.

References

• Category:Electronic design automation: Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting[TIM] Cheng