为加权图着色的特例

Question

问题是：我有一个图 G，其中每个顶点都标有一些非负数（权重），我必须找到非负数的子集 S最大化其标签之和的相邻顶点（G的独立集合）（我们称之为W(S)，子集的权重S）。

我想到了图形着色的世界，但在这种情况下，问题是只使用两种颜色为图形着色，白色用于选择的顶点，黑色用于其他，因此只有白色顶点必须是非相邻，同时它们的总权重最大化（或者如果我们使所有标签均为负则最小化）。

这个具体问题有名字吗？我发现最接近的是 cocoloring，但它们不适用于加权图。

Answer 1

看看独立集 (https://en.wikipedia.org/wiki/Independent_set_(graph_theory))。您的特定问题是最大权重独立集问题。