【文件属性】：
文件名称：基于极大独立集搜索的独立集算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2021-06-09 22:34:49
集训队论文集
3.1 基于极大独立集搜索的独立集算法
3.1.1 朴素的搜索算法
最朴素的搜索算法非常简单：用深度优先搜索枚举 V 的子集 I ⊆ V，即按一定顺序枚
举每个点 v ∈ V 是否属于 I，一旦存在 (u, v) ∈ E 使得 u, v ∈ I，就回溯。输出枚举的所有独
立集 I 中，|I|最大的一个。该算法的复杂度为 O(2nm)，效率太低。
针对最大独立集这一问题，可以进行一些剪枝。例如：
1. 若 deg(v) = 0，则不存在与 v关联的边，故总可以令 v ∈ I。
2. 若 deg(v) = 1，考虑唯一的与 v关联的结点 u，若 u < I，则总可以令 v ∈ I；否则，从
I 中删去 u并加入 v，I 的大小不变。因此总可以令 v ∈ I。
8导出子图有点导出子图和边导出子图两种，本文中均指前者。
9Robson在2001年提出了一种复杂度约 O(1.1888n)的最大独立集算法，见参考文献[2]。
33