Сепараторы в графах: различия между версиями

Многие задачи можно решить, используя подпрограммы поиска сбалансированного сепаратора или самого неплотного сечения. Коэффициент аппроксимации полученного алгоритма обычно прямо зависит от коэффициента соответствующей подпрограммы. В большинстве случаев граф рекурсивно разбивается на фрагменты сбалансированного размера. Помимо коэффициента аппроксимации O(log n), принадлежащего алгоритму поиска сбалансированного сепаратора, еще один коэффициент O(log n) возникает в силу глубины рекурсии. Ивен и др. [12] улучшили многие результаты на базе алгоритма сбалансированного сепаратора благодаря использованию метрик рассеяния, снизив гарантированный коэффициент аппроксимации с O(log2 n) до O(log n log log n).

• Линейное расположение минимального разреза и минимальное множество обратных дуг. Обе эти задачи решает один алгоритм O(log n)-аппроксимации.

• Построение минимального хордального графа и упорядочение удалений [ 1 ]. Упорядочение удалений используется при решении разреженных систем линейных уравнений с симметричной матрицей. Коэффициент O(log n) аппроксимации [ ] для построения хордального графа был улучшен до O(log n log log n) Ивеном и др. [12].

• Проектирование СБИС. Бхатт и Лейтон [ ] изучали несколько задач оптимизации для проектирования СБИС. Рекурсивное разбиение при помощи алгоритма поиска сбалансированного сепаратора ведет к созданию полилогарифмических алгоритмов аппроксимации для нахождения количества пересечений, минимальной площади размещения схемы и других задач.

• Древесная ширина и путевая ширина. Бодлендер и др. [9] показали способ аппроксимации древесной ширины с коэффициентом O(log n) и путевой ширины – с коэффициентом O(log2 n) при помощи сбалансированных вершинных сепараторов.

 

• Бисекция.  Файги и Краутгамер [7] предложили O(log n)-аппроксимацию задачи минимальной бисекции при помощи любого алгоритма a-аппроксимации для нахождения минимального сечения.