文件名称：寻找最大独立集的启发式算法：输出最大基数的独立集。 在 O(n^2) 时间内运行，n=图形大小。-matlab开发
文件大小：2KB
文件格式：ZIP
更新时间：2024-06-21 07:54:18
matlab
findMIS 是一种用于解决最大独立集问题 (MIS) 的启发式算法。 图的独立集是顶点的子集，其中没有两个顶点是邻近的。 给定一组顶点，最大独立集问题调用用于找到最大基数的独立集。 算法在 O(n^2) 时间内运行，其中 n 是顶点数（最坏情况）。 实验上：时间 = 8.1e-007*n^2 + 2.2e-005*n + 0.00012 秒，（见截图） 该算法是独立开发的，但类似于： Balaji、Swaminathan、Kannan，“一种简单的优化算法最大独立集”，高级建模和优化，第 12 卷，第 1 期，2010 年符号： v 的邻域由 N(v) ={u in V 定义，使得 u 与 v 相邻} V 中顶点 v 的度数，用 deg(v) 表示，由v. 的邻居V 中顶点 v 的 SUPPORT 由顶点的度数之和定义与 v 相邻，即 support(v) = s(v) = su
【文件预览】：
findMIS.zip