最大独立集合問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/13 08:08 UTC 版)
最大独立集合問題(さいだいどくりつしゅうごうもんだい)は、グラフ理論において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの(独立集合)で大きさが最大のものを求める問題。最大安定集合問題とも言う。この問題は、NP困難であることが知られている。
- 1 最大独立集合問題とは
- 2 最大独立集合問題の概要
- 最大独立集合問題のページへのリンク