Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Реализация) |
Irina (обсуждение | вклад) |
||
| Строка 99: | Строка 99: | ||
== Применение == | == Применение == | ||
Многие задачи можно решить, используя подпрограммы поиска сбалансированного сепаратора или самого неплотного сечения. Коэффициент аппроксимации полученного алгоритма обычно прямо зависит от коэффициента соответствующей подпрограммы. В большинстве случаев граф рекурсивно разбивается на фрагменты сбалансированного размера. Помимо коэффициента аппроксимации O(log n), принадлежащего алгоритму поиска сбалансированного сепаратора, еще один коэффициент O(log n) возникает в силу глубины рекурсии. Ивен и др. [12] улучшили многие результаты на базе алгоритма сбалансированного сепаратора благодаря использованию метрик рассеяния, снизив гарантированный коэффициент аппроксимации с <math>O(log^2 \; n)</math> до O(log n log log n). | Многие задачи можно решить, используя подпрограммы поиска сбалансированного сепаратора или самого неплотного сечения. Коэффициент аппроксимации полученного алгоритма обычно прямо зависит от коэффициента соответствующей подпрограммы. В большинстве случаев граф рекурсивно разбивается на фрагменты сбалансированного размера. Помимо коэффициента аппроксимации O(log n), принадлежащего алгоритму поиска сбалансированного сепаратора, еще один коэффициент O(log n) возникает в силу глубины рекурсии. Ивен и др. [12] улучшили многие результаты на базе алгоритма сбалансированного сепаратора благодаря использованию [[метрика рассеяния|метрик рассеяния]], снизив гарантированный коэффициент аппроксимации с <math>O(log^2 \; n)</math> до O(log n log log n). | ||
| Строка 106: | Строка 106: | ||
• Линейное расположение минимального разреза и минимальное множество обратных дуг. Обе эти задачи решает один алгоритм <math>O(log^2 \; n)</math>-аппроксимации. | • Линейное расположение минимального разреза и минимальное множество обратных дуг. Обе эти задачи решает один алгоритм <math>O(log^2 \; n)</math>-аппроксимации. | ||
• Построение минимального хордального графа и упорядочение удалений [1]. Упорядочение удалений используется при решении разреженных систем линейных уравнений с симметричной матрицей. | • Построение минимального хордального графа и упорядочение удалений [1]. Упорядочение удалений используется при решении разреженных систем линейных уравнений с симметричной матрицей. Алгоритм с коэффициентом аппроксимации <math>O(log^2 \; n)</math> [1] для построения хордального графа был улучшен до O(log n log log n) Ивеном и др. [12]. | ||
• Сбалансированные вершинные сечения. Стоимость сбалансированного сечения может измеряться в терминах веса вершин, удаленных из графа. Алгоритм поиска сбалансированного сепаратора можно легко расширить на такой случай с взвешенными вершинами. | • Сбалансированные вершинные сечения. Стоимость сбалансированного сечения может измеряться в терминах веса вершин, удаленных из графа. Алгоритм поиска сбалансированного сепаратора можно легко расширить на такой случай с взвешенными вершинами. | ||
• Проектирование СБИС. Бхатт и Лейтон [8] изучали несколько задач оптимизации для проектирования СБИС. Рекурсивное разбиение при помощи алгоритма поиска сбалансированного сепаратора ведет к созданию полилогарифмических алгоритмов аппроксимации для нахождения количества пересечений, минимальной площади размещения схемы и других | • Проектирование СБИС. Бхатт и Лейтон [8] изучали несколько задач оптимизации для проектирования СБИС. Рекурсивное разбиение при помощи алгоритма поиска сбалансированного сепаратора ведет к созданию полилогарифмических алгоритмов аппроксимации для нахождения количества пересечений, минимальной площади размещения схемы и других показателей. | ||
• Древесная ширина и путевая ширина. Бодлендер и др. [9] показали способ аппроксимации древесной ширины с коэффициентом O(log n) и путевой ширины – с коэффициентом <math>O(log^2 \; n)</math> при помощи сбалансированных вершинных сепараторов. | • [[Древесная ширина]] и [[путевая ширина]]. Бодлендер и др. [9] показали способ аппроксимации древесной ширины с коэффициентом O(log n) и путевой ширины – с коэффициентом <math>O(log^2 \; n)</math> при помощи сбалансированных вершинных сепараторов. | ||
• Бисекция. Файги и Краутгамер [7] предложили <math>O( \alpha \; log \; n)</math>-аппроксимацию задачи минимальной бисекции при помощи любого алгоритма <math>\alpha \;</math>-аппроксимации для нахождения минимального сечения. | • Бисекция. Файги и Краутгамер [7] предложили <math>O( \alpha \; log \; n)</math>-аппроксимацию задачи минимальной бисекции при помощи любого алгоритма <math>\alpha \;</math>-аппроксимации для нахождения минимального сечения. | ||