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

Ссылки сюда (4) →

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.