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

Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [ ]. Быстрые алгоритмы 2-аппроксимации для задач k-ECSS и k-VCSS изучали Нагамочи и Ибараки [13]. Алгоритмы на базе DFS для задачи 2-связности были предложены Хуллером и Вишкином [11]. Они получили следующие коэффициенты аппроксимации: 3/2 для задачи 2-ECSS, 5/3 для 2-VCSS и 2 для взвешенной k-ECSS. Значение коэффициента для 2-VCSS было улучшено в следующих работах: до 3/2 – Гарг и коллеги [6], до 4/3 – Вемпала и Ветта [14], до 9/7 – Губбала и Рагавачари [ ]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [ ] изучали задачу k-VCSS для взвешенных ребер и разработали алгоритм аппроксимации сложности O(log k) для графов, содержащих не менее 6k2 вершин.

Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [ ]. Они предложили алгоритмы с коэффициентами 1 + \ для k-VCSS, 1 + -^ для k-ECSS, 1 + 1 для k-VCSS в ориентированных графах и 1 + p4 для k-ECSS в ориентированных графах. Вемпала и Ветта [ ] сумели получить коэффициент 4/3 для задачи 2-VCSS. Далее результат улучшили Криста и Кумар [ ], предложившие гибридный подход, при помощи которого Джоти и коллеги разработали алгоритм с коэффициентом 5/4. [ ]. Алгоритм 3/2-аппроксимации для задачи 3-ECSS, предложенный Габовым [ ], работает на мультиграфах, тогда как более ранний алгоритм Черияна и Туримеллы позволяет получить такое же значение коэффициента только на простых графах. Губбала и Рагавачари улучшили это значение до 4/3 [8].