Geodesic
Estimating the Number of s-t Paths in a Graph
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 195-214.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The problem of counting the number of s-t paths in a graph is #P-complete. We provide an algorithm to estimate the solution stochastically, using sequential importance sampling. We show that the method works effectively for both graphs and digraphs. We also use the method to investigate the expected number of s-t paths in a random graph of size n and density d, and develop a model that shows how this quantity behaves when n and d are varied. 
@article{JGAA_2007_11_1_a7,
     author = {Ben Roberts and Dirk Kroese},
     title = {Estimating the {Number} of s-t {Paths} in a {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {195--214},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00142},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00142/}
}
TY  - JOUR
AU  - Ben Roberts
AU  - Dirk Kroese
TI  - Estimating the Number of s-t Paths in a Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 195
EP  - 214
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00142/
DO  - 10.7155/jgaa.00142
LA  - en
ID  - JGAA_2007_11_1_a7
ER  - 
%0 Journal Article
%A Ben Roberts
%A Dirk Kroese
%T Estimating the Number of s-t Paths in a Graph
%J Journal of Graph Algorithms and Applications
%D 2007
%P 195-214
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00142/
%R 10.7155/jgaa.00142
%G en
%F JGAA_2007_11_1_a7
Ben Roberts; Dirk Kroese. Estimating the Number of s-t Paths in a Graph. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 195-214. doi : 10.7155/jgaa.00142. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00142/

Cité par Sources :