Counting cycles on planar graphs in subexponential time

DOI10.1007/s00453-023-01182-4OpenAlexW4388094543MaRDI QIDQ6182684

Jin-Yi Cai, Ashwin Maran

Publication date: 25 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01182-4

zbMATH Keywords

planar graphsMotzkin pathscounting cyclesplanar separator

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Finding small simple cycle separators for 2-connected planar graphs
• Reduced constants for simple cycle graph separation
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• A Separator Theorem for Planar Graphs
• Planar Separators
• Enumeration of the Elementary Circuits of a Directed Graph
• Finding All the Elementary Circuits of a Directed Graph
• An efficient search algorithm to find the elementary circuits of a graph
• Self-avoiding walks crossing a square
• Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
• Motzkin numbers