The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.

DOI10.1016/S0304-3975(03)00080-XzbMath1051.68116WikidataQ29029689 ScholiaQ29029689MaRDI QIDQ1401394

Seinosuke Toda, Maciej Liśkiewicz, Ogihara, Mitsunori

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

self-avoiding walks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Some observations on holographic algorithms ⋮ Pentagonal chains and annuli as models for designing nanostructures from cages ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ Packing 1-plane Hamiltonian cycles in complete geometric graphs ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ The complexity of counting models of linear-time temporal logic ⋮ Counting substrate cycles in topologically restricted metabolic networks ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ Unnamed Item

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A linear-time algorithm for drawing a planar graph on a grid
• A very hard log-space counting class
• Enumerating up-side self-avoiding walks on integer lattices
• Tally NP sets and easy census functions.
• Self-testing algorithms for self-avoiding walks
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Statistical mechanics, three-dimensionality and NP-completeness
• PP is as Hard as the Polynomial-Time Hierarchy
• The complexity of congestion-1 embedding in a hypercube
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• The Complexity of Enumeration and Reliability Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Complexity of Planar Counting Problems
• A note on succinct representations of graphs
• Relationships among $PL$, $\#L$, and the determinant
• The complexity of satisfiability problems
• FURTHER RESULTS ON THE RATE OF CONVERGENCE TO THE CONNECTIVE CONSTANT OF THE HYPERCUBICAL LATTICE

This page was built for publication: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.