内存保守最大独立顶点集

Question

我想找到一个内存保守但有效的算法，用于在无向图中设置最大独立顶点。

传统算法使用辅助数据结构（原始图的副本）来实现它。我想避免这种并行结构，因为内存分配在实时实现上很慢，而且我有一些内存边界。 我只想用布尔标签在MIS中标记节点。 这可能吗？

请注意，我不希望最大独立但最大独立设置。

P.S. 我知道这个问题是独立于语言的，但我用C++和STL编码。

Answer 1

很难回答这种问题，而不知道你的数据结构究竟是什么。近似就地图操作的常用技巧是窃取两位，否则指针将为零，并对图结构进行可逆更改，但我不确定它们在这里如何应用。

通过阅读你所写的内容，似乎没有办法在没有遍历的情况下遍历图中的节点。你如何代表DFS的堆栈？

Answer 2

这里是一个解决方案，如果你只有你的布尔标签（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 

标签（v）= true的节点v是最大独立集合。它们是独立的，因为每个构建标记的节点v都不能有标记的邻居。而且它们是最大集合，因为您只激活标签，并且只有另一个已标记的邻居才能阻止该标签，并且只留下未标记的节点。

优化说明：如果节点编号为1 ... n，则只需检查邻居w = 1..v-1，因为其他任何w都不能有标签（w）= true。

Answer 3

我使用一个临时vector或用来表示其顶点由元素，或边缘，或者使用方面deque<bool>，...

std::deque<bool> used(vertex.size(), false); 
for (size_t e = 0; e < edge.size(); ++e) 
{ 
    used[edge[e].v1] = true; 
    used[edge[e].v2] = true; 
} 

现在使用== true表示所有用过的顶点。如果你愿意，其他人可能会崩溃。