Fiduccia–Mattheyses algorithm

<h2 id="introduction">Introduction</h2>
<p>FM algorithm is a linear time heuristic for improving network partitions.
New features to <a href="/facts/Kernighan%E2%80%93Lin_algorithm/oJ5F0dN5">K-L heuristic</a>:
</p>
<ul><li>Aims at reducing net-cut costs; the concept of cutsize is extended to hypergraphs.</li>
<li>Only a single  vertex is moved across the cut in a single move.</li>
<li>Vertices are weighted.</li>
<li>Can handle "unbalanced" partitions; a balance factor is introduced.</li>
<li>A special data structure is used to select vertices to be moved across the cut to improve running time.</li>
<li>Time complexity <i>O</i>(<i>P</i>), where <i>P</i> is the total # of terminals.</li></ul>

<h2 id="fm-heuristic-notation">F–M heuristic: notation</h2>
<p>Input: A hypergraph with a vertex (cell) set and a hyperedge (net) set
</p>
<ul><li>n(i): # of cells in Net i; e.g., n(1) = 4</li>
<li>s(i): size of Cell i</li>
<li>p(i): # of pins of Cell i; e.g., p(1) = 4</li>
<li>C: total # of cells; e.g., C = 13</li>
<li>N: total # of nets; e.g., N = 4</li>
<li>P: total # of pins; P = p(1) + … + p(C) = n(1) + … + n(N)</li>
<li>Area ratio r, 0< r<1</li></ul>
<p>Output: 2 partitions 
</p>
<ul><li>Cutsetsize is minimized</li>
<li>|A|/(|A|+|B|) ≈ r</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Graph_partition/MSQF0WyD">Graph partition</a></li>
<li><a href="/facts/Kernighan%E2%80%93Lin_algorithm/oJ5F0dN5">Kernighan–Lin algorithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Fiduccia; Mattheyses (1982). "A Linear-Time Heuristic for Improving Network Partitions". 19th Design Automation Conference. pp. 175–181. doi:10.1109/DAC.1982.1585498. ISBN 0-89791-020-6. Retrieved 23 October 2013. <a href="0-89791-020-6" target="_blank">0-89791-020-6</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Fiduccia–Mattheyses algorithm open-in-new

Fiduccia–Mattheyses algorithm