、平面（<em>N</em>が偶数）に<em>N</em>点を考える平面

Question

上のN点の各々に対してk個のリンクの総距離を最小限に抑え、K（K < Nを生成する効率的なアルゴリズムがあります）各点からの接続kグローバルな距離が最小限に抑えられている他の点は？例えば

、= 2 N = 4とKでこれoptimal resultこのnon-optimal resultよりも好ましいであろう。

グローバル距離は、接続された距離の合計です。ノードは完全に接続する必要はありません（島は問題ありません）。

Answer 1

あなたが記述した問題はGraph Factorizationと呼ばれ、あなたが探しているのはグラフの最小コストkマッチングです。あなたはそれを解決するために強く多項式の時間アルゴリズムを提供するRichard P. Anstee, A polynomial algorithm for b-matchings: An alternative approach, 1987を読むことによって進むことができます。