Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00142 Estimating the Number of s-t Paths in a Graph Ben Roberts and Dirk P. Kroese Vol. 11, no. 1, pp. 195-214, 2007. Regular paper Abstract 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.
|
Revised: April 2007. Submitted: September 2006. Communicated by Susanne Albers |
| Journal of Graph Algorithms and Applications |