The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
From MaRDI portal
Publication:1401394
DOI10.1016/S0304-3975(03)00080-XzbMath1051.68116WikidataQ29029689 ScholiaQ29029689MaRDI QIDQ1401394
Ogihara, Mitsunori, Maciej Liśkiewicz, Seinosuke Toda
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
Related Items
Uses Software
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
