ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Spiridonov 2:5020/400 07 Mar 2002 18:55:04
To : sena73@narod.ru
Subject : Re: Клика в графе
--------------------------------------------------------------------------------
"Ihor Bobak" <ibobak@svitoch.lviv.ua> writes:
> Извините, что не впервые задаю этот вопрос, но в первый раз никто не
> ответил.
>
> Кто-нибудь знает нормальный алгоритм (не полным перебором) для нахождения
> максимальной клики (полносвязного подмножества с максимальным количесвом
> вершин)
> в графе ?
>
> Буду очень благодарен за любую информацию.
Задача о клике является NP полной. Доказательство есть например в
"Introduction to Algorithms" Thomas H. Cormen и др. (есть русский перевод
"Алгоритмы построение и анализ").
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Senasoft (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Клика в графе 
