Geodesic
The number of Euler tours of a random $d$-in/$d$-out graph
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

In this paper we obtain the expectation and variance of the number of Euler tours of a random $d$-in/$d$-out directed graph, for $d \geq 2$. We use this to obtain the asymptotic distribution and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every $d$-in/$d$-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of a $d$-in/$d$-out graph is the product of the number of arborescences and the term $[(d-1)!]^n/n$. Therefore most of our effort is towards estimating the asymptotic distribution of the number of arborescences of a random $d$-in/$d$-out graph. 
@article{DMTCS_2010_special_258_a23,
     author = {Creed, P\'aid{\'\i} and Cryan, Mary},
     title = {The number of {Euler} tours of a random $d$-in/$d$-out graph},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2787},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2787/}
}
TY  - JOUR
AU  - Creed, Páidí
AU  - Cryan, Mary
TI  - The number of Euler tours of a random $d$-in/$d$-out graph
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2787/
DO  - 10.46298/dmtcs.2787
LA  - en
ID  - DMTCS_2010_special_258_a23
ER  - 
%0 Journal Article
%A Creed, Páidí
%A Cryan, Mary
%T The number of Euler tours of a random $d$-in/$d$-out graph
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2787/
%R 10.46298/dmtcs.2787
%G en
%F DMTCS_2010_special_258_a23
Creed, Páidí; Cryan, Mary. The number of Euler tours of a random $d$-in/$d$-out graph. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2787. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2787/

Cité par Sources :