Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the C chordless cycles contained in an undirected graph G = (V,E) takes O(|E|~2 + |E|·C) time. In this paper we provide an algorithm taking O(|E| + |V| · C) time. We also show how to obtain the same complexity for listing all the P chordless st-paths in G (where C is replaced by P).
展开▼
机译：无弦循环是无向图中非常自然的结构，具有重要的历史和图论中的杰出作用。出于以前关于列表循环经典问题的研究的动机，我们研究了如何列出无弦循环。列出无向图G =（V，E）中包含的所有C个无弦循环的最著名解决方案需要O（| E |〜2 + | E |·C）时间。在本文中，我们提供了一种耗费O（| E | + | V |·C）时间的算法。我们还展示了如何获得列出G中所有P个无弦st路径的相同复杂度（其中C替换为P）。
展开▼
