5

約 100 個の頂点を持つ完全なグラフ (少なくとも 1 つの弦を持つ奇数サイクルを持つグラフ) で最大のクリークのサイズを見つけるための高速アルゴリズム ??

これは完全なグラフであり、多項式時間の解があるはずなので、ブルートフォースよりも簡単な方法はありますか。しかし、アルゴリズムを見つけることができません。

貪欲な色付けは、すべての完全なグラフで最適な色付けを行いますか??

4

2 に答える 2

3

100頂点？プフフト。Cliquer を使用すると、数秒 (おそらく数分の 1 秒) で力ずくで攻撃できます。 http://users.tkk.fi/pat/cliquer.html

于 2010-06-11T06:50:49.287 に答える
1

296 ページを参照してください。この問題を解決するには、適切な線形計画法制約を作成する必要があります。

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

于 2010-06-11T05:51:04.410 に答える