在无向图的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.

在什么时刻，我应该申请和？

是否有更详细的解释在这个算法中去除假周期？

Answer 1

我认为其意图是在计算两个周期的异或以获得一个新周期之前，检查并确保它们不是不相交的。这是因为两个不相交周期的XOR是两个不相交的周期，而这不是你想要的。

事实上，我认为将AND与XOR阶段相结合更有效率 - 为了计算XOR，您需要识别属于两个周期的边以排除它们。所以只要跟踪是否丢弃任何边缘，如果你没有，那么你没有找到一个新的循环。