重み付けされた無向2部グラフの最大重み付けマッチングを計算するためのさまざまなアルゴリズムを知っています(つまり、割り当ての問題)。
たとえば...ハンガリーアルゴリズム、ベルマンフォード法、またはブロッサムアルゴリズム(一般的な、つまり2部グラフではない)でさえ機能します。
ただし、2部グラフのエッジに重みが付けられ、方向付けられている場合、最大の重み付きマッチングを計算するにはどうすればよいですか?
前述のアルゴリズムのいずれかを適用できるように、グラフを無向にするための、多項式の複雑さを備えたアルゴリズムまたは事前の変換へのポインターをいただければ幸いです。
編集:マッチングはエッジの重みを最大化する必要があることに注意してください。そのため、有向エッジがあると違いが生じます(A->BはB->Aとはまったく異なる重みを持つ可能性があります)。
確かに、カーディナリティを最大化する場合、有向エッジは違いをもたらさず、カーディナリティを最大化するためによく知られたアルゴリズムのいずれかを適用できます:ホップクロフト-カープ、最大ネットワークフロー...。
編集2:マッチングは通常無向グラフに適用される用語なので、この質問でマッチングすることによって正確に何を意味するのかを明確にしましょう:開始頂点または終了頂点を共有しない有向エッジのセット。より正式には、U->VとU'-> V'がマッチングの一部である場合、V /=U'とV'/=Uです。