Overview
Fiduccia-Mattheyses is a partition-refinement heuristic that improves Kernighan-Lin-style partitioning by moving one vertex at a time and updating gains with efficient bucket structures.
ExtendedSource checked
Fiduccia-Mattheyses Algorithm
Refines network or graph partitions with efficient single-vertex moves.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Advanced
- Family
- Graph partitioning
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Not ready
- Aliases
- FM algorithm, Fiduccia-Mattheyses partitioning
Core Concepts
graph partitioninghypergraph partitioninggain bucketslocal search
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + m) per pass with suitable gain buckets
Average
O(n + m) per pass with suitable gain buckets
Worst
O(n + m) per pass with suitable gain buckets
Space
O(n + m)
When to Use
- Use when single-vertex move refinement is more practical than pairwise swaps.
When Not to Use
- Do not treat it as a proof of optimal partition quality.
What It Does
- Tracks gain values for moving vertices between partitions.
- Uses efficient bucket structures to select promising moves.
- Improves graph or hypergraph partition cut quality.
Use Cases
- VLSI partitioning
- Hypergraph partitioning
- Balanced graph cuts
Inputs
- A graph or network partition with balance constraints and move gains.
Outputs
- A refined partition with improved cut or connectivity cost.
Pseudocode
- 1.Initialize move gains.
- 2.Select an unlocked vertex with high gain.
- 3.Move and lock it.
- 4.Update neighboring gains.
- 5.Apply the best improving prefix.
Canonical Example
- Input
- A graph or hypergraph with an initial balanced partition.
- Output
- A refined partition with lower cut cost.
- Explanation
- The method moves vertices according to gain while preserving balance constraints.
Implementation Notes
- Bucket data structures are central to the expected efficiency gains.
Common Pitfalls
- Ignoring balance constraints can produce invalid partitions.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow single-vertex moves, gain buckets, balance constraints, and the best improving move prefix.
Step 1 of 5: Initialize move gains.
partition-refinementNotes
Fiduccia-Mattheyses is usually discussed as partition refinement for networks or hypergraphs; wording should stay clear about the model being used.
Sources (2)
What each reference supports for this entry.
Fiduccia and Mattheyses (1982)
PaperSupports the linear-time network partition improvement heuristic and gain-update refinement mechanism.
Open sourceDBLP Fiduccia-Mattheyses record
DocumentationBibliographic metadata for the 1982 Design Automation Conference paper and DOI.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageImproves onKernighan-Lin Algorithm
Fiduccia-Mattheyses refines Kernighan-Lin-style partitioning with single-vertex moves and gain-bucket updates.
Related Algorithms
Tags
GraphOptimizationLocal Search