首页 > 其他 > 详细

找最大独立集问题-Finding a Maximal Independent Set

时间:2014-06-10 06:29:43      阅读:404      评论:0      收藏:0      [点我收藏+]

1. 独立集和最大独立集:A set of vertices I ? V is called independent if no pair of vertices in I is connected via an edge in G. An independent set is called maximal if by including any other vertex not in I, the independence property is violated.

    下图是独立集和最大独立集的例子:

bubuko.com,布布扣

2. Finding a Maximal Independent Set (MIS) 

1) Simple algorithms start byMIS I to be empty, and assigning all vertices to a candidate set C. Each vertex generates a(unique) random number and communicates it to its neighbors.
2) If vertex v‘s number less than that of all its neighbors, it joins set I. All of its neighbors are removed from C.
3) This process continuesuntil C is empty.

    On average, this algorithmconverges after O(log|V|) such steps. 下图是找MIS的例子:

bubuko.com,布布扣

找最大独立集问题-Finding a Maximal Independent Set,布布扣,bubuko.com

找最大独立集问题-Finding a Maximal Independent Set

原文:http://blog.csdn.net/xin_jmail/article/details/29597471

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!