non*_*one 2 algorithm graph-theory
用语言,有人可以发布在简单图中找到"最大"独立集的方向吗？
我从ETH网站上读到了一些东西,它说可以在O(n)中找到这样的东西,只需选择一个随机顶点v,然后扫描其余的并试图找出是否有从v到其余部分的边缘.
谢谢
小智 5
是的,根据定义,最大独立集是一个独立集,在不违反"独立性"条件的情况下,不能再添加顶点.
因此,只需选择顶点直到你不再选择将给你一个最大的独立集合,可以在线性时间内完成(即线性在| V | + | E |).
注意,这与最大独立集不同,最大独立集是最大可能大小的独立集合,并且发现是NP-Hard.