Problem Detail: Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices? Relevant results on special graphs could also be helpful.
Asked By : liuyu
Answered By : vzn
calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/characteristics of the graphs you’re studying.]
- Computing the average path length and a label-based routing in a small-world graph — Philippe J. Giabbanelli, Dorian Mazauric, and Stephane Perennes
- Average path length in random networks — Agata Fronczak, Piotr Fronczak, Janusz A. Holyst
- The average distance in a random graph with given expected degrees — Fan Chung, Linyuan Lu
- AN ESTIMATION OF THE SHORTEST AND LARGEST AVERAGE PATH LENGTH IN GRAPHS OF GIVEN DENSITY — Laszlo Gulyas, Gabor Horvath, Tamas Cseri and George Kampis
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11146
