1

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パッケージでオープンソースにすることを計画しています。

4

1 に答える 1

0

0-extension の目的は、さまざまな色のエンドポイントを持つエッジの総加重コストを最大化することではなく、最小化することです。そのため、0-extension は実際にはカラーリングの問題ではなくクラスタリングの問題です。私は一般的に、クラスタリング アルゴリズムを使用して色を付けると良い結果が得られるかどうか懐疑的です。理論的な保証が必要な場合は、MAXCUT 問題 (2 つ以上の色がある場合は実際には一般化) の近似を調べることができますが、実際にはローカル検索アルゴリズムの方がうまく機能すると思います。

于 2011-04-25T21:44:33.883 に答える