algorithm - 解释0-扩展算法

Question

我正在尝试实现 0 扩展算法。

它用于用多种颜色为图形着色，其中一些节点已经分配了颜色并且每条边都有一个距离。该算法计算颜色分配，使具有相同颜色的相邻节点之间的距离尽可能远。

我找到这篇解释算法的论文:http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=1FBA2D22588CABDAA8ECF73B41BD3D72?doi=10.1.1.100.8049&rep=rep1&type=pdf但我不明白我需要如何实现它。

我已经在“理论计算机科学”网站上问过这个问题，但讨论到一半就超出了网站的范围: https://cstheory.stackexchange.com/questions/6163/explain-0-extension-algorithm

谁能通俗地解释一下这个算法？我打算在 jgrapht 包中开源最终代码。

Answer 1

0-extension 的目标是最小化具有不同颜色端点的边的总加权成本而不是最大化它，因此 0-extension 实际上是一个聚类问题而不是着色问题。我通常怀疑使用聚类算法来着色是否会产生好的结果。如果您想要一些有理论保证的东西，您可以研究 MAXCUT 问题的近似值(如果有两种以上的颜色，这实际上是一种概括)，但我怀疑局部搜索算法在实践中会更好。