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

Возможно, из-за связи с первоначальной задачей первые алгоритмы минимальной триангуляции были основаны на упорядочении и давали в результате порядок, называемый минимальным порядком удаления. С тех пор задача нахождения минимальной триангуляции получила широкое распространение; были опубликованы несколько новых вариантов применения и характеризаций, касающихся свойств разделителей вершин. В числе таких новых вариантов применения – нахождение древесной ширины графа и реконструкция эволюционной истории при помощи филогенетических деревьев [6]. Новые характеризации минимальной триангуляции на основе разделителей вершин повысили уровень знаний о минимальных триангуляциях [1,7,9]. Одним из результатов, основанных на этих характеризациях, является алгоритм вычисления древесной ширины графа за полиномиальное время в случае, когда количество минимальных разделителей полиномиально ограничено [2]. Другим вариантом применения являются более быстрые точные алгоритмы вычисления древесной ширины графа с полиномиальным временем исполнения [4].