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