解釋0擴展算法

我試圖實現0擴展算法。解釋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包中製作最終代碼開源代碼。

來源

2011-04-25 Berty

0擴展的目的是爲了使最小化不同顏色端點的邊的總加權代價而不是最大化它，所以0-擴展確實是一個聚類問題，而不是一個着色問題。我一般都懷疑使用聚類算法進行顏色處理會有很好的效果。如果你想要一些理論保證的東西，你可以看看MAXCUT問題的近似值（如果有兩種以上的顏色，真的是泛化），但我懷疑在實踐中本地搜索算法會更好。

來源

2011-04-25 21:44:33 qrqwe

我試過MAXCUT算法無法處理預着色節點，還是隻需要更通用的算法版本？我當前的實施方案（使用分支搜索進行優化）在12分鐘內計算3個顏色的35個節點，我需要在10分鐘內租用64個節點 – Berty 2011-04-27 06:44:25

對於兩種顏色，您只需強制執行與預着色節點相對應的向量具有的約束點積-1。一般來說，用k種顏色，你想要-1 /（k-1），但是四捨五入變得更加棘手。我會嘗試使用分離預着色節點的ceil（lg k）隨機超平面。 – qrqwe 2011-04-27 16:21:05

解釋0擴展算法

回答

相關問題