Жадный алгоритм покрытия для почти всех исходных данных/Задачи/Жадное вершинное покрытие для почти всех исходных данных — различия между версиями

Версия 13:14, 23 декабря 2011

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых

• n-вершин
• ребра между любой парой вершин возникают с вероятностью p.

Какова точность алгоритма для почти всех исходных данных?

(упрощенный вариант — для фиксированного p=½).