On the number of Eulerian orientations of a graph

DOI10.1007/BF01940872zbMath0861.68066OpenAlexW2002234069MaRDI QIDQ1923856

Milena Mihail, Peter M. Winkler

Publication date: 13 October 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940872

zbMATH Keywords

Eulerian graphEulerian orientation

Mathematics Subject Classification ID

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

Related Items

Asymptotic behavior of the number of Eulerian orientations of graphs, Bounding the number of Eulerian tours in undirected graphs, Conditional exact tests for Markovianity and reversibility in multiple categorical sequences, Refined bounds on the number of Eulerian tours in undirected graphs, Beyond windability: approximability of the four-vertex model, Unnamed Item, Complexity classification of the six-vertex model, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, Number of spanning trees of different products of complete and complete bipartite graphs, Eulerian digraphs and toric Calabi-Yau varieties, On the Query Complexity of Testing Orientations for Being Eulerian, A faster FPTAS for counting two-rowed contingency tables, The Potts model and the Tutte polynomial, Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence, Sampling and Counting 3-Orientations of Planar Triangulations, Sampling Eulerian orientations of triangular lattice graphs, Spanning trees of descendants of a complete graph, A dichotomy for real weighted Holant problems

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Geometric bounds for eigenvalues of Markov chains
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the permanent of graphs with large factors
• On the computational complexity of the Jones and Tutte polynomials