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

Обобщив этот алгоритм, можно решить задачу 2-VCSS с тем же коэффициентом аппроксимации, если добавлять тщательно отобранные обратные ребра, позволяющие удалять древесные ребра. В случае, когда удалить древесное ребро невозможно, алгоритм добавляет вершину к множеству независимых вершин I. В конечном итоге количество использованных ребер будет меньше n + jIj. Поскольку Opt не меньше max(n; 2jIj), мы получаем аппроксимацию с коэффициентом 3/2.

Алгоритм можно расширить на задачу вычисления k-ECSS, применяя этот подход k/2 раз и на каждом этапе увеличивая число связей на 2. Было показано, что описанный алгоритм достигает эффективности 1.61.