scientific article; zbMATH DE number 742958

MaRDI QIDQ4763400zbMATH OpenFDO

Authors Milena Mihail, Peter Winkler

Publication date 11 April 1995

zbMATH Keywords

perfect matchingscountingTutte polynomialEulerian graphEulerian orientationsEulerian toursmonotonicity lemmanear-perfect matchingsrandomized schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30)

Recommendations

• On the number of Eulerian orientations of a graph
• Sampling Eulerian orientations of triangular lattice graphs
• scientific article; zbMATH DE number 2127753
• Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids
• Random sampling of Euler tours

Cited in

(22)

• Counting the Eulerian orientations of one class of circulant graphs
• Counting degree-constrained subgraphs and orientations
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Exact counting of Euler tours for generalized series-parallel graphs
• Random sampling of Euler tours
• Counting planar Eulerian orientations
• Approximating the number of monomer-dimer coverings of a lattice.
• scientific article; zbMATH DE number 2127753 (Why is no real title available?)
• FPT algorithms exploiting carving decomposition for Eulerian orientations and ice-type models
• Factor-of-iid balanced orientation of non-amenable graphs
• Eulerian digraphs and toric Calabi-Yau varieties
• Oriented Euler complexes and signed perfect matchings
• Graphs with many strong orientations
• Counting Euler tours in undirected bounded treewidth graphs
• Covers, orientations and factors
• Asymptotic behavior of the number of Eulerian orientations of graphs
• Several constants arising in statistical mechanics
• Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids
• On the Query Complexity of Testing Orientations for Being Eulerian
• A theory of even functionals and their algorithmic applications
• On the number of dissimilar pfaffian orientations of graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4763400)