在一个简单的图中找到'最大'独立集的算法

有人可以通过单词发布方向来找到'最大'独立集吗？在一个简单的图中找到'最大'独立集的算法

我从ETH网站上读到了一些东西，他说O（n）可以通过简单地选取一个随机顶点v并扫描其余部分并试图找出是否存在从v到其余的边缘。

感谢

来源

2010-06-03 none

是的，顾名思义，最大indpendent组是一个可以在不违反“独立”的条件不能添加更多的顶点独立设置。因此，只要选择顶点，直到你不能选择最多的独立集合，就可以在线性时间内完成（即线性| | | | | | E |）。

注意，这是从最大独立集，它是一个独立的一套尽可能大的规模和发现，是NP难的不同。

来源

2010-06-03 02:29:51

但是这是O（m^2），其中m是您找到的独立集合的大小。对于边缘很少的图形，它接近O（n^2）。 – Artelius 2010-06-03 02:52:43

它的边数是线性的在图形问题中，表示很重要，线性通常意味着| V | + | E |从技术上讲，输入的大小可能大于| V | + | E |。对不起，如果不明确。我将编辑答案。 – 2010-06-03 03:10:23

NP-Hard，这是否意味着不存在伪P解决方案？ – 2010-06-03 13:59:32

发现这个在网络上，可能是由一类” 陪文本``介绍并行计算‘’，艾迪生韦斯利，2003

找到一个极大独立集（MIS）

parallel MIS algorithms use randimization to gain 
concurrency (Luby's algorithm for graph coloring). 

Initially, each node is in the candidate set C. Each 
node generates a (unique) random number and 
communicates it to its neighbors. 

If a nodes number exceeds that of all its neighbors, it 
joins set I. All of its neighbors are removed from C. 

This process continues until C is empty. 

On average, this algorithm converges after O(log|V|) 
such steps.

来源

2014-03-11 10:43:25 Marichyasana

在一个简单的图中找到'最大'独立集的算法

回答

相关问题