4430
правок
Связность графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Литература
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→Литература) |
||
| Строка 48: | Строка 48: | ||
== Литература == | == Литература == | ||
Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [3]. Быстрые алгоритмы 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 – Губбала и Рагавачари [7]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [ ] изучали задачу k-VCSS для взвешенных ребер и разработали аппроксимационный алгоритм со сложностью O(log k) для графов, содержащих не менее <math>6k^2 \;</math> вершин. | Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [3]. Быстрые алгоритмы 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 – Губбала и Рагавачари [7]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [2] изучали задачу k-VCSS для взвешенных ребер и разработали аппроксимационный алгоритм со сложностью O(log k) для графов, содержащих не менее <math>6k^2 \;</math> вершин. | ||
Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [1]. Они предложили алгоритмы с коэффициентами <math>1 + \frac{1}{k}</math> для k-VCSS, <math>1 + \frac{2}{k+1}</math> для k-ECSS, <math>1 + \frac{1}{k}</math> для k-VCSS в ориентированных графах и <math>1 + \frac{4}{ \sqrt{k} }</math> для k-ECSS в ориентированных графах. Вемпала и Ветта [14] сумели получить коэффициент 4/3 для задачи 2-VCSS. Далее результат улучшили Криста и Кумар [12], предложившие гибридный подход, при помощи которого Джоти и коллеги разработали алгоритм с коэффициентом 5/4 [9]. Алгоритм 3/2-аппроксимации для задачи 3-ECSS, предложенный Габовым [5], работает на мультиграфах, тогда как более ранний алгоритм Черияна и Туримеллы позволяет получить такое же значение коэффициента только на простых графах. Губбала и Рагавачари улучшили это значение до 4/3 [8]. | Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [1]. Они предложили алгоритмы с коэффициентами <math>1 + \frac{1}{k}</math> для k-VCSS, <math>1 + \frac{2}{k+1}</math> для k-ECSS, <math>1 + \frac{1}{k}</math> для k-VCSS в ориентированных графах и <math>1 + \frac{4}{ \sqrt{k} }</math> для k-ECSS в ориентированных графах. Вемпала и Ветта [14] сумели получить коэффициент 4/3 для задачи 2-VCSS. Далее результат улучшили Криста и Кумар [12], предложившие гибридный подход, при помощи которого Джоти и коллеги разработали алгоритм с коэффициентом 5/4 [9]. Алгоритм 3/2-аппроксимации для задачи 3-ECSS, предложенный Габовым [5], работает на мультиграфах, тогда как более ранний алгоритм Черияна и Туримеллы позволяет получить такое же значение коэффициента только на простых графах. Губбала и Рагавачари улучшили это значение до 4/3 [8]. | ||