The complexity of counting Eulerian tours in 4-regular graphs
From MaRDI portal
Publication:2429360
DOI10.1007/s00453-010-9463-4zbMath1236.68091arXiv1009.5019MaRDI QIDQ2429360
Publication date: 26 April 2012
Published in: Algorithmica, LATIN 2010: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.5019
\#P-complete; Eulerian tours; fully polynomial randomized approximation scheme; A-trails; AP-reduction
05C30: Enumeration in graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C45: Eulerian and Hamiltonian graphs
Related Items
Counting single-qubit Clifford equivalent graph states is #P-complete, A dichotomy for real weighted Holant problems, The complexity of counting Eulerian tours in 4-regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- On non-intersecting Eulerian circuits
- Eulerian graphs and related topics. Part 1, Volume 1
- Mixing times of lozenge tiling and card shuffling Markov chains
- The relative complexity of approximate counting problems
- The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
- The complexity of counting Eulerian tours in 4-regular graphs
- Random sampling of Euler tours