ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Stanislav Shwartsman                 2:400/520      27 Nov 2001  22:12:34
 To : Vitaly Osipov
 Subject : Клика в графе?
 -------------------------------------------------------------------------------- 
 

 
 27 Nov 01 12:00, you wrote to All:
 
  VO> Задан обыкновенный граф, найти в нем клику - максимальный полный
  VO> подграф. Мне кроме перебора ничего в голову не идет :( Может есть что
  VO> похитрее?
 
  Это одна из классических NP-полных задач. То есть решения за
  полиномиальное время еще никто в мире не нашел и все известные
  решения этой задачи работают за время const*<полный перебор>.
 
     E-mail: gate@fidonet.org.il
     Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
 
 Bye !
 Stanislav     (AKA Night's Man)                        [Team Technion]
 ---
  * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
 
 

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

Тема:    Автор:    Дата:    Клика в графе?   Vitaly Osipov   27 Nov 2001 13:00:50   Клика в графе?   Stanislav Shwartsman   27 Nov 2001 22:12:34   Клика в графе?   Vitaly Osipov   28 Nov 2001 19:20:47