「色の交差」の数を最小限にするための頂点の色付け/割り当て

Question

割り当て/線形プログラミングの問題のように実際に「着色」問題であるかどうかはわかりません。私はどちらも専門知識がないので、それに続く可能性のある迷いを赦してください。しかし、私はこの問題がほぼ確実に解決されていなければならないという気持ちを持っています。私はちょうどhttp://en.wikipedia.org/wiki/Category:Graph_algorithmsのグラフアルゴリズムの多くを調べた後に何かを見つけることができませんでした。私は正しい方向にいくつかの指針を得ることを望んでいた。ルータやコア：グラフの頂点の2種類があります

1. ：

   「問題文は」効果的に沸きます。

2. コアはルータにのみ接続されます。各コアは、単一のルータにのみ接続されています。また、それぞれにはユーザー入力/定義された「色」があります。 （私の特定の問題では、色は4/5の可能な色の1つに限定されています）。色は変更できません。入力パラメータです。 （コアは下の画像の四角形です）

3. ルータはコアや他のルータに接続されています。彼らには「色」が割り当てられていません。色を割り当てることは、プログラム/アルゴリズムの目的の一部です。

4. プログラムの目的は、グラフ内の各ルータに、異なる色の頂点間の「交差」/辺の数を最小限に抑えるように色を割り当てることです。

（代替ビュー：本質的に、あなたは、いくつかの頂点が着色されているグラフが与えられ、他のものではない目的は、異なる色の頂点間の辺の数ようでないものを着色することです。 ）

私はInteger-Linear-Programとしてこれを公式化することはできましたが、LP-Solveを使って解決策やアプローチを設定しました。私も自分のヒューリスティックを持っています。私はこれを解決するための "適切な" /既知の/他のアプローチを知りたいですか？

多くのありがとうございます！

Answer 1

色< = 5とルータ< = 10の数は、あなたは、ブルートフォースを使用することができます。

5つ以上のオプションがあります。特に、デフォルトではすべてのルータに最も一般的な色を割り当てて、必要に応じてバックグラウンドで色を変更します。

編集：ハミルトニアンパスアルゴリズムもあります.15台未満のルータがあれば、必要に応じて適応することができます。 What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

Answer 2

まず2色のケースに注目しましょう。これをs-tmin cutのインスタンスにすることができます。アイデアは、我々はグラフ中Sノードとトンノードを指定していることを、我々はS基又はトン基のいずれかに残りのノードを分割することは、そのようなものの和ということです2つのグループ間のエッジ重みが最小限に抑えられます。あなたのバージョンでは、マスター黄色ノードsとマスター赤ノードtがあります。各コアと対応するマスターカラーノードの間に元のグラフのすべてのエッジのカウントを超える高い重み付きエッジを配置し、オリジナルのエッジはすべて元のウェイト1です。コストの高いエッジは、すべてのルータを移動するのに安くなるため、コアを不正に再コーディングすることはありません。この問題はstandard max flow algorithmsを使用してMax flow-Min cut theoremを使用して多項式時間で解くことができます。最適な選択は、エッジと頂点数によって異なります。

複数の色の場合、「マルチターミナルカット」問題を解決しようとしています。これはminimum k-cut問題に関連していますが、この問題の標準的な参考文献は、という論文（これはkです）は、論文が間接的にリンクしています。 2色以上の場合、グラフが平面であると明らかに、問題は多項式時間で解くことができます。それ以外の場合はNP-hardなので、整数プログラミングソルバーを使用することもできます。これはNP困難な問題です。