これやってる人いるかな。普通に気になる。
平面グラフ from yutaka1999
www.slideshare.net
yutaka1999氏のスライドがあり、平面グラフ判定は本気を出すとでできるなどと書かれていてびっくりする。
Max-Cut
e-archive.informatik.uni-koeln.de
平面グラフでのMax-Cutはらしい。速すぎ
Max-Cutのベンチマーク
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1941-09.pdf
現時点での最速？ http://mauricio.resende.info/doc/gmaxcut.pdf
数万頂点程度
実験するなら平面グラフと一般グラフの両方でやりたいね
平面グラフでもNP-hardな問題
ほとんど。。。Max-CliqueはPだけど自明すぎてア
Independent Set (Vertex Cover), Dominating Set, Feedback Vertex Set, Traveling Salesperson Problem...
Feedback Vertex Set
http://www.eda.ce.titech.ac.jp/ueno/Files/papers/TTU12-ICNC.pdf
Degree at most 3系ではいくつか簡単なアルゴリズムもあるっぽい
It is known that MinFVS is NP-hard for bigraphs while it can be solved in time for chordal bipartite graphs, in
time for convex graphs, and in
time for permutation graphs.
らしい。すご（やっぱそんなにうれしくねえ）
