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

Материал из DISCOPAL
< Жадный алгоритм покрытия для почти всех исходных данных
Версия от 13:14, 23 декабря 2011; StasFomin (обсуждение | вклад) (Created page with "Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра ...")

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_покрытия_для_почти_всех_исходных_данных/Задачи/Жадное_вершинное_покрытие_для_почти_всех_исходных_данных&oldid=1107»