Algorithms to count paths and cycles

DOI10.1016/0020-0190(94)00151-0zbMath0815.68077OpenAlexW2059105688MaRDI QIDQ1339379

Eric T. Bax

Publication date: 1 December 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00151-0

zbMATH Keywords

pathsHamiltonian cyclescounting cycles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Stability structures of conjunctive Boolean networks ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Number of cycles of small length in a graph ⋮ Complexity of counting cycles using zeons ⋮ A finite-difference sieve to count paths and cycles by length ⋮ Open problems around exact algorithms ⋮ Solving the train marshalling problem by inclusion-exclusion ⋮ Enumerating simple paths from connected induced subgraphs

Cites Work

• The complexity of computing the permanent
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Dynamic programming meets the principle of inclusion and exclusion
• The Complexity of Enumeration and Reliability Problems
• Enumeration of the Elementary Circuits of a Directed Graph
• Unnamed Item
• Unnamed Item