вершинное покрытие

DLW63

Подскажите, плз, эффективный алгоритм для приближенного решения. Простой метод жадности или выбор произвольного ребра не подходят.
Может в частном случае графа с не очень большими степенями вершин можно что-нибудь придумать?

toxin

Гугл дает ссылку на эту страницу - http://iitam.omsk.net.ru/~eremeev/papers_r.htm . Там вроде сами статьи в формате ps выложены. Под рукой ps просмотрщика нету, поэтому проверить их разумность не могу.

DLW63

Спасибо, нашла там крайне полезные ссылки
Оставить комментарий
Имя или ник:
Комментарий: