4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 81: | Строка 81: | ||
Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого | Алгоритмы из вышеприведенных теорем используют (в качестве черного ящика) алгоритм аппроксимации для задачи под названием «разрез с минимальным частным» или эквивалентной ей задачи нахождения самого разреженного сечения с равномерным спросом (?). Лучших из известных на данный момент алгоритмов аппроксимации с коэффициентом <math>O( \sqrt{log \; n})</math> для решения этой задачи для графов общего вида предложили Арора, Рао и Вазирани [2], а алгоритм для графов, не включающих фиксированный минор, с временем выполнения O(1) – Кляйн, Плоткин и Рао. Эти алгоритмы аппроксимации для вычисления разреза с минимальным частным позволяют получить алгоритм аппроксимации по двум критериям с полиномиальным временем выполнения (иногда называемый алгоритмом псевдоаппроксимации) для решения задачи о минимальной бисекции. Например, для графов общего вида алгоритм гарантированно вычисляет 2/3-сбалансированный разрез со стоимостью не более <math>O( \sqrt{log \; n}) \cdot b(G)</math>. Отметим, впрочем, что 2/3-сбалансированный разрез не является хорошей аппроксимацией для значения b(G). Например, если граф G состоит из трех непересекающихся клик равного размера, оптимальный 2/3-сбалансированный разрез не содержит ребер, тогда как <math>b(G) = \Omega(n^2) \;</math>. Информацию о других работах в этом направлении, включая алгоритмы аппроксимации для плотных графов, для ориентированных графов, а также для других задач о разбиении графов см. в главе 1 [6] и по ссылкам, приведенным в этой работе. | ||
== Применение == | == Применение == | ||
Строка 111: | Строка 111: | ||
*'' [[Сепараторы в графах]] | *'' [[Сепараторы в графах]] | ||
*'' [[Самое | *'' [[Самое разреженное сечение]] | ||
правка