無指向性グラフアルゴリズムの結果のDFS-XORサイクル検出での誤ったサイクルの削除

Question

私はthis paperで定義されたアルゴリズムを実装していましたが、結果から誤ったサイクルを削除する方法を得ることはできません。紙から

引用： The method will find non-existing cycles in case there are no overlapping edges at all between the two cycles in base. This can be fixed by first applying AND on each two cycles in base.

何現時点では私は適用しなければなりませんか？

このアルゴリズムでは、false-cylesの削除の詳細な説明はありますか？

Answer 1

私は、新しいサイクルを得るために2サイクルの排他的論理和を計算する直前に、それらが分離していないことを確認することを意図していると思います。これは、2つの独立したサイクルの排他的論理和が2つの独立したサイクルであり、これはあなたが望むものではないためです。

実際、XORを計算するためには、両方のサイクルに属するエッジを特定して除外する必要があるため、ANDとXORステージを組み合わせる方が効率的だと思います。だから、あなたがエッジを捨てたかどうかを追跡してください。そうでなかったら、新しいサイクルを見つけられませんでした。