Fiduccia–Mattheyses algorithm


A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Charles Fiduccia and Robert Mattheyses. 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, where P is the total # of terminals.

F–M heuristic: notation

Input: A hypergraph with a vertex set and a hyperedge set
  • n: # of cells in Net i; e.g., n = 4
  • s: size of Cell i
  • p: # of pins of Cell i; e.g., p = 4
  • C: total # of cells; e.g., C = 13
  • N: total # of nets; e.g., N = 4
  • P: total # of pins; P = p + … + p = n + … + n
  • Area ratio r, 0< r<1
Output: 2 partitions
  • Cutsetsize is minimized
  • |A|/ ≈ r