A general purpose algorithm for counting simple cycles and simple paths of any length

DOI10.1007/s00453-019-00552-1zbMath1423.05171arXiv1612.05531OpenAlexW3098109735MaRDI QIDQ2415361

Richard C. Wilson, Nils M. Kriege, Pierre-Louis Giscard

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.05531

zbMATH Keywords

networksself-avoiding walksdigraphsself-avoiding polygonslabeled graphsconnected induced subgraphssimple pathssimple cycleselementary circuits

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (4)

Stability structures of conjunctive Boolean networks ⋮ Number of cycles of small length in a graph ⋮ A Hopf algebra for counting cycles ⋮ Evolution of cooperation for multiple mutant configurations on all regular graphs with \(N \leq 14\) players

Uses Software

• Matlab
• KONECT

Cites Work

• Sparsity. Graphs, structures, and algorithms
• The complexity of computing the permanent
• Complexity of counting cycles using zeons
• A finite-difference sieve to count paths and cycles by length
• Finding and counting given length cycles
• The number of \(n\)-cycles in a graph
• The problem of isolating and counting
• Dynamic programming meets the principle of inclusion and exclusion
• Algorithms to count paths and cycles
• What's in a crowd? Analysis of face-to-face behavioral networks
• Enumerating simple paths from connected induced subgraphs
• Immanantal invariants of graphs
• Reverse search for enumeration
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Single-hook characters and hamiltonian circuits^∗
• Emergence of Scaling in Random Networks
• Planar Subgraph Isomorphism Revisited
• The Complexity of Enumeration and Reliability Problems
• On Algorithms for Enumerating All Circuits of a Graph
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The Parameterized Complexity of Counting Problems
• Finding All the Elementary Circuits of a Directed Graph
• A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
• Optimal Listing of Cycles and st-Paths in Undirected Graphs
• Counting Subgraphs via Homomorphisms
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A general purpose algorithm for counting simple cycles and simple paths of any length