最大独立集合

keyword:vertexcover, independentSet

カートに追加

overview

グラフの最大独立集合の大きさと選ぶ頂点集合を求める. 入力グラフは単純グラフであること.多重辺はNG. 最小頂点被覆,最大クリークに転用可能. 分岐限定法. note: verifiedのリンク先のコードはランダム生成による検証コードを含む

usage

int independentSet(const Graph& graph)

verified

https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/4080519

references

FV Fomin, Exact Exponential Algorithms, Springer.

require

code