Fiduccia-Mattheyses

Gebipartitioneerde graaf met knipgrootte = 2

Fiduccia-Mattheyses is een algoritme om een lokale zoekactie uit te voeren.

Deze methode wordt gebruikt bij het graaf-bipartioneringsprobleem (zie Grafentheorie). Hierbij is het doel het de twee kleuren van de knopen van de graaf zo aan te passen zodat er zo min mogelijk knopen van verschillende kleur met elkaar verbonden zijn. Het aantal knopen dat met elkaar verbonden is en een andere kleur bezit noemt met de knipgrootte.

Algoritme

Het algoritme begint met een gebalanceerde graaf (evenveel 'witte' en 'zwarte' knooppunten)

1. Wissel de zwarte knoop van kleur die de knipgrootte het meest verkleint
2. Wissel de witte knoop van kleur die de knipgrootte het meest verkleint
3. Fixeer beide knopen
4. Herhaal stap 1 t/m 3 totdat er geen vrije knopen meer zijn.
5. Ga nu terug naar de situatie waarbij de knipgrootte minimaal is.
6. Herhaal stap 1 t/m 6 totdat deze geen verbetering meer opleveren.
7. Nu is er een lokaal optimum gevonden.

Snelheid

Fiduccia-Mattheyses geïmplementeerd met een bucket-array is constant in de tijd ten opzichte van het aantal verbindingen O(N).