Алгоритм LBFS*, Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов - Алгоритмы нескольких махов

Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы дополнительные алгоритмы. Одним из таких алгоритмов является алгоритм LBFS* [6]. В нем на этапе выборки из множества вершин с наибольшими лексикографическими метками используются дополнительные параметры, сосчитанные по предыдущему этапу LBFS. Пусть граф с вершинами и порядок (последовательность) вершин. Обозначим множество (закрытое множество соседей вершины минус вершина ) и пустое множество. Обозначим число как.

Пусть множество вершин с лексикографически наибольшим номером.

Пусть и

Пусть некоторая вершина такая что

Необходимая вершина выбирается следующим образом: когда иначе когда и когда

Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов

Этапы алгоритма [6]:

Д <LBFS

У <LBFS+(д)

Расчет и для всех вершин

С <LBFS*(у)

Ф <LBFS+(с)

Если ф является UI порядком, то граф единичный интервальный;

Если ф является I порядком, то граф интервальный, иначе "граф не интервальный".

Следует отметить, что в данном алгоритме на каждом из 6 этапов выполняется полный обход вершин и ребер графа, то есть условно данный алгоритм "шестимаховый".

Похожие статьи




Алгоритм LBFS*, Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов - Алгоритмы нескольких махов

Предыдущая | Следующая