The complexity of counting Eulerian tours in 4-regular graphs

DOI10.1007/s00453-010-9463-4zbMath1236.68091arXiv1009.5019OpenAlexW2099831741MaRDI QIDQ2429360

Qi Ge, Daniel Štefanković

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

zbMATH Keywords

\#P-completeEulerian toursfully polynomial randomized approximation schemeA-trailsAP-reduction

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

Bounding the number of Eulerian tours in undirected graphs ⋮ Counting single-qubit Clifford equivalent graph states is #P-complete ⋮ The complexity of counting Eulerian tours in 4-regular graphs ⋮ Refined bounds on the number of Eulerian tours in undirected graphs ⋮ A dichotomy for real weighted Holant problems

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

This page was built for publication: The complexity of counting Eulerian tours in 4-regular graphs