Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.

So this is the setup: -the graph is fully connected

-the graph is directed

-number of states are given

-number of edges are given

-the graph displays a markovchain, so all outgoing edges of a node have to be 1, summed up

-there is one input node and one output node, no more absorbing states

before the algorithm starts i want to estimate the probability of the most probable path.

I was thinking about: what is the most probable graph structure, what would be the average connectivity and how would the probability distribution be.

like I said before I'm new to this, so this might be stupid or to easy or impossible :P

share|cite|improve this question
Sorry, but this site is for questions in research-level mathematics. –  Brendan McKay Oct 25 '12 at 14:42

1 Answer 1

My just published book , " A New Algorithm for Studying Routes in a Connected Graph', Kindle Edition, by Amazon. Com may be helpful in your problem. My new algorithm does not employ search, recursion or AI. It is based on combinatorial Analysis/Block Design. My algorithm produces all routes of length (PL) between the starting node, s and all other nodes. The number of such routes is simply Avg(Nc)^PL where Avg(Nc) is average degree of nodal connectivity. My software package (EcoNets) also selects routes (simple or cyclic) between any two nodes s and t. It can also select any routes with any set of route-attributes such as distance, link costs or reliabilities. A sample network (10n, 20s) took about 1 minute of my laptop and about 1 Gigabytes of RAM for all routes with PL <=10. If you go to website, you can peruse the sample pages of my book and study the algorithm. Wish you luck.

share|cite|improve this answer
This site is not for advertising. –  Brendan McKay Oct 25 '12 at 14:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.