ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey V. Smirnov                    2:5020/400     03 Feb 2003  16:06:13
 To : Alexey V. Smirnov
 Subject : Re: Задача наибольшего независимого множества вершин (или ребер)
 -------------------------------------------------------------------------------- 
 

 > Изветсно, что сабж - HП-полная задача.
 > Hикак не могу найти доказательство этого.
 > И оценку сложности алгоритма решения в символике о-большого.
 
 задача вроде бы решается с помощью переборного метода Брона
 а вот оценить сложность не могу... наверняка есть где-то подобные
 выкладки..
 -- 
 best regards,
 Alexey V. Smirnov (aka ASM), asm@quorus.ru
 Developer,
 Special Software Department,
 Quorus ACS,
 Ekaterinburg.
 
 P.S. "Ищу поклонников Microsoft.... Hайду - убью!" :)
 --- ifmail v.2.15dev5
  * Origin: Quorus ACS (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Задача наибольшего независимого множества вершин (или ребер)   Alexey V. Smirnov   03 Feb 2003 15:38:51   Re: Задача наибольшего независимого множества вершин (или ребер)   Alexey V. Smirnov   03 Feb 2003 16:06:13