Random sampling of Euler tours

Authors
Tetali, P Vempala, S
Citation
P. Tetali et S. Vempala, Random sampling of Euler tours, ALGORITHMIC, 30(3), 2001, pp. 376-385
Citations number
14
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
30
Issue
3
Year of publication
2001
Pages
376 - 385
Database
ISI
SICI code
0178-4617(200107)30:3<376:RSOET>2.0.ZU;2-F
Abstract
We define a Markov chain on the set of Euler tours of a given Eulerian grap h based on transformations first defined by Kotzig in 1966. We prove that t he chain is rapidly mixing if the maximum degree in the given graph is 6, t hus obtaining an efficient algorithm for sampling and counting the set of E uler tours for such an Eulerian graph.