c++ - 内存保守最大独立顶点集

Question

我想为无向图中的最大独立顶点集找到一种内存保守但高效的算法。

传统算法使用辅助数据结构(原始图的拷贝)来实现它。我想避免这种并行结构，因为内存分配对于实时实现来说很慢，而且我有一些内存边界。 我只想用 bool 标签标记 MIS 中的节点。 可能吗？

请注意，我不想要最大独立集，而是最大独立集。

附言 我知道这个问题与语言无关，但我使用 C++ 和 STL 进行编码。

Answer 1

如果您只有每个节点 i 的 bool 标签 (i)，这是一个解决方案。它需要时间 O(|V|+|E|)，其中 |V|是节点数，|E|是输入图中的边数。

For all nodes v
   set label(v)=false;
For all nodes v
   if (all neighbors w of v have label(w)=false)
      set label(v)=true

label(v)=true 的节点 v 是一个最大独立集。它们是独立的，因为根据构造，任何带标签的节点 v 都不能有带标签的邻居。它们是一个最大集合，因为您只激活标签，并且如果另一个已经标记的邻居 w 阻止它，则只留下一个节点 v 未标记。

优化说明:如果节点编号为 1...n，您只需检查邻居 w=1..v-1，因为任何其他 w 都不能具有 label(w)=true。