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

Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу сбалансированного сепаратора. Разбиение (S, V \ S) графа G называется c-сбалансированным сепаратором для <math>0 < c < \frac{1}{2}</math>, если и S, и V \ S имеют не менее c|V| вершин. Задача о сбалансированном разделителе состоит в том, чтобы найти сбалансированное c-разбиение с минимальной разреженностью. Эта разреженность обозначается как <math>\alpha_c(G)</math>.