有向グラフで最大ウェイトの回路を見つけるアルゴリズムとは何ですか？

Question

最初の問題は、有向グラフを入力として与えた場合、グラフに存在するすべてのサイクルのリストを出力として与えるアルゴリズムを見つけることができなかったことです。 （この問題はNP完全でなければなりません）。

しばらくの間、問題を考えた後、最大の重み（エッジの重さの合計）でサーキット（重複した頂点を持つことができますが、重複しないエッジ）を見つけることが本当に必要なことに気付きました。

これはNP完全な問題でもあります。進行する方法は、グラフに存在するすべての回路をリストし、エッジ重みの合計でソートすることです。

グラフに出力されているすべての回路のリストを出力するアルゴリズムを知っていますか？または最大の重量を持つ回路を見つけるもの？

私はこれを見つけましたが、それは私が必要とするものではありません。

http://epubs.siam.org/doi/abs/10.1137/0205007

は、しかし、あなたはこれらの問題の計算の複雑さを確認するのですか？

Answer 1

あなたは可能です。ここのように：Finding all cycles in a directed graph。

すべてのノードについてこの検索を行い、実行時間を短縮するためにそれを並列化します。その後、各サイクルがノードのリストであるサイクルリストに効率的なソートアルゴリズムを適用します。ソートアルゴリズムはMergesortやQuicksortのようなものかもしれませんが、好きなものを選んでください。

私はそれを楽しみにしています。