有向非巡回グラフで最小パス カバーを計算するための効率的なアルゴリズムが存在するかどうかを知りたいです。最小の「パス カバー」を「頂点ディスジョイント パス カバー」と混同しないでください。後者については、対応する二部グラフの最大マッチングを使用する効率的なアルゴリズムを知っています。ただし、これは頂点が素の場合にのみ適用されます。各頂点を複数回訪れることができる場合、同じアルゴリズムを緩和してパス カバーの答えを取得できますか?
質問する
2304 次