|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Spiridonov 2:5020/400 11 Mar 2002 19:50:32
To : sena73@narod.ru
Subject : Re: Клика в графе
--------------------------------------------------------------------------------
"Ihor Bobak" <ibobak@svitoch.lviv.ua> writes:
> > Задача о клике является NP полной. Доказательство есть например в
> > "Introduction to Algorithms" Thomas H. Cormen и др. (есть русский перевод
> > "Алгоритмы построение и анализ").
>
> Знаю, что эта задача - NP полная.
>
> Hадо приблизительный быстрый алгоритм (ищущий близкое к оптимальному
> решение) работающий за полиномиальное время.
Цитируя Кормена:
"...если бы для задачи о клике существовал приближённый алгоритм с
ошибкой не более С раз (для некоторого фиксированного С), то для этой
задачи существовала бы полностью полиномиальная схема приближения
[Как установлено в работе S. Arora and S. Safra, Approximating clique
is NP-complete, Proceeding of the 33rd IEEE Symp. on Foundation of
Computer Science, 1992, такое возможно, лишь если P=NP."
--
Best regards, Sergey Spiridonov
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Senasoft (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
