Нахождение макс. клики в идеальных графиках

Алгоритм FAST для нахождения размера самой многочисленной клики в идеальном графике (этот имеющий нечетные циклы по крайней мере с 1 хордой) приблизительно с 100 вершинами??

И есть ли любой более простой метод, чем грубая сила, как это - идеальный график и должно быть полиномиальное решение времени его. Но я не могу найти алгоритм.

Жадная окраска дает оптимальное раскрашивание всех идеальных графиков??

5
задан copperhead 11 June 2010 в 07:02
поделиться

2 ответа

100 вершин? Пффф. Перебор за несколько секунд (возможно, доли секунды) с помощью Cliquer. http://users.tkk.fi/pat/cliquer.html

3
ответ дан 15 December 2019 в 00:50
поделиться

См. Стр. 296, поработав, вы должны написать правильное ограничение линейного программирования для решения этой проблемы.

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

1
ответ дан 15 December 2019 в 00:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: