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

'''Алгоритм вычисления k-ECSS с коэффициентом <math>1 + \frac{2}{k+1}</math>'''. Теорема Мадера о циклах, порожденных критическими ребрами, действует только для вершинной связности, но не для реберной. В силу этого был предложен отдельный алгоритм для вычисления k-ECSS в графах, являющихся k-реберно-связными, но не являющихся k-связными. Этот алгоритм находит подграф <math>D_k \;</math> минимальной мощности и дополняет его минимальным количеством добавочных ребер, делая подграф k-реберно-связным. Количество ребер, добавленных на последнем этапе, не превышает £^у(и — 1). Поскольку количество добавленных на первом этапе ребер не превышает Opt, общее число ребер в итоге не превышает (1+k + j

Улучшенные алгоритмы для малых значений k. Для k 2 f2; 3g алгоритмы были улучшены за счет более аккуратного применения вышеизложенных действий, удаления не являющихся необходимыми ребер и получения улучшенных нижних границ. Для k = 2 может быть получена аппроксимация с коэффициентом 4/3 при помощи формирования покрытия путями и циклами с минимальной мощностью (D2) и 2-связывания их к «основному» компоненту, по одному на каждом шагу. Небольшие циклы и пути позволяют удалять ребро, когда они 2-связаны с ядром, что обеспечивает возможность применения простого амортизационного анализа. Можно обобщить этот метод на задачу 3-ECSS и получить аппроксимацию с коэффициентом 4/3.

Были предложены гибридные подходы, использующие покрытие путями и циклами для создания специфического DFS-дерева исходного графа и затем организации 2-связного дерева за счет удаления ребер везде, где это возможно. Использование таких подходов позволяет получить следующие коэффициенты аппроксимации в лучшем случае: 5/4 для задачи 2-ECSS, 9/7 для 2-VCSS и 5/4 для 2-VCSS в 3-связных графах.