Fiduccia-Mattheyses algorithm

A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Fiduccia and Mattheyses.[1] 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:

F-M Heuristic: Notation

Input: A hypergraph with a vertex (cell) set and a hyperedge (net) set

Output: 2 partitions

See also

References

  1. Fiduccia; Mattheyses (1982). "A Linear-Time Heuristic for Improving Network Partitions" (PDF). 19th Design Automation Conference. Retrieved 23 October 2013.
This article is issued from Wikipedia - version of the Tuesday, January 20, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.