Итерационные алгоритмы разрезания применяются для улучшения начальной компоновки, полученной в результате исполнения последовательных алгоритмов. В графе, разрезанном на подграфы, производится парная перестановка элементов разных подграфов с проверкой на каждом шаге приращения числа ребер, соединяющих куски. Цель итераций — минимизация числа соединительных ребер.. Один из основных итерационных алгоритмов включает следующие процедуры:
1°. Из всего множества подграфов, полученных в результате разрезания, выбираются любые два. Например, (, ) и (, ). Для каждой пары вершин подсчитывается значение Δ (разность между числом новых внешних связей после перестановки и и числом прежних внешних связей до перестановки).
2°. Те пары вершин, для которых Δ<0, заносятся в список замены элементов, а пары вершин, для которых Δ>0, в список не заносятся и в дальнейшем не рассматриваются.
3°. Переставляются между собой вершины и , для которых Δ минимально (если их несколько, то переставляется любая из этих пар).
4°. Переставленные вершины отмечаются и повторяется процесс подсчета Δ для вновь образованных подграфов *1(, ) и (, ) с замененными вершинами, причем Δ для отмеченных, т. е. переставленных вершин, не подсчитывается.
5°. Повторяются 2°, 3°, 4° до тех пор, пока в списке замены не окажется таких пар, для которых Δ<0, после чего процесс перестановки вершин выбранных подграфов заканчивается. Переходят к п. 6°.
6°. Все отметки переставленных вершин рассмотренных подграфов и устраняются. Выбирается любая другая пара подграфов и для вновь выбранных подграфов повторяются пп. 1°—5°, т. е. минимизируется число соединений для вновь выбранных подграфов.
Процесс повторяется, пока не будут сделаны перестановки во всех парах подграфов графа (, ). Число таких пар будет равно числу сочетаний из элементов по два: (—1)/2 ( — число подграфов).