Быстрая минимальная триангуляция: различия между версиями

Минимальные триангуляции были впервые описаны в середине семидесятых, и с тех пор было предложено множество алгоритмов. Полный обзор алгоритмов и различные характеризации хордальных графов и минимальных триангуляций можно найти в работе Хеггернеса и коллег [5], посвященной минимальным триангуляциям. Алгоритмы минимальных триангуляций можно грубо разделить на алгоритмы, получающие триангуляцию посредством упорядочивания удалений, и алгоритмы, получающие ее при помощи разделителей вершин. Большинство этих алгоритмов имеют время исполнения <math>O(nm) \; </math>, что для плотных графов превращается в <math>O(n^3) \; </math>. Среди алгоритмов, использующих упорядочение удалений, самым быстрым на данный момент является алгоритм Кратча и Спинрада с временем исполнения <math>O(n^{2.69}) \; </math> [8]. Из алгоритмов, использующих разделители вершин, самым быстрым является алгоритм Хеггернеса и коллег [5] с временем исполнения <math>o(n^{2.376}) \; </math>, [5]. подробнее описанный ниже. И алгоритм Кратча и Спинрада [8], и алгоритм Хеггернеса и коллег используют алгоритм матричного умножения Копперсмита и Винограда [3], который позволяет получить алгоритм с временем исполнения o(n3).

Алгоритм быстрой минимальной триангуляции FMT. Дано: произвольный граф G = (V, E). Требуется: найти минимальную триангуляцию G0 графа G.

Пусть Q1, Q2 и Q3 – пустые очереди; поместить G в Q1; G0 = G; repeat