utros 02.06.2011 18:37 Adium

Няши, хорошо ориентирующиеся в англоязычных математических и программерских интернетах, помогите пожалуйста найти алгоритм (или его описание) для точного решения задачи о минимальном вершинном покрытии (я знаю что она NP-полная).
Порекомендуйте пожалуйста, ибо горит, а моя глупая голова уже ничего не соображает.

math, help, solved
#sisof
re 9 comments !recommend ~bookmark Ssubscribe
1. vt 02.06.2011 18:40 Home

ачо википедия не оно? http://en.wikipedia.org/wiki/Vertex_cove...

#sisof/1
rereply
2. 3axap 02.06.2011 18:40 35975592011306965767394529

Пососёшь — помогу.

#sisof/2
rereply
3. utros → vt /1 02.06.2011 18:41 Adium

Там только про приближенные полиномиальные методы. Мне нужен точный (пусть и экспоненциальный).

#sisof/3
rereply
4. utros 02.06.2011 18:54 Adium

А, всё ок. Нашел описание, но пока не нашел хоть какой-нить работающей реализации =(

#sisof/4
rereply
5. jtootf 02.06.2011 19:04 lagrange

http://en.wikipedia.org/wiki/Knuth's_Alg... http://en.wikipedia.org/wiki/Dancing_Lin...

#sisof/5
rereply
6. utros → jtootf /5 02.06.2011 19:05 Adium

О, спасибо большое. Когда буду в Харькове, с меня ништяки.

#sisof/6
rereply
7. jtootf → utros /6 02.06.2011 19:08 lagrange

телепортацией из Харькова в Киев? :)

#sisof/7
rereply
8. utros → jtootf /7 02.06.2011 19:10 Adium

Значит риальне туплю. Почему-то думал, что ты из Харькова.
s/в Харькове/в Киеве/ и далее по тексту :)

#sisof/8
rereply
9. jtootf → utros /8 02.06.2011 19:12 lagrange

ок!

#sisof/9
rereply
Do you really want to delete ?