0
私は有向グラフのすべてのサイクルがNP完全であることを見出しましたが、グラフのすべての単純なサイクルを見つけるJohnsonのアルゴリズムはO（（V + E）（C + 1） ）時間（ここで、Cはグラフの強く接続されたコンポーネントの数です）、これは多項式だと思っています（E < = V^2とO 0122ジョンソンのアルゴリズムはどのように多項式ではありませんか？
ジョンソンのアルゴリズム：http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
あなたの質問は、http：//cs.stackexchange.com/より適切です。たとえば、[この質問]（http://cs.stackexchange.com/questions/59331/is-finding-all-cycles-in-a-graph-using-some-version-of-johnsons-algorithm-code）を参照してください。 。 – Renzo