casais@uni2a.unige.ch (11/07/90)
Several weeks ago, I posted the following enquiry:
Is there a mathematical (statistical) characterization
of the length and number of paths between the nodes of
a directed graph without circuits ?
What I wanted was actually the known bounds on the average
pathlength and number of paths in a DAG, or for special families
of directed graphs. Here is what I have been able to find; it is
not much. The literature on the subject is scarce, as several persons
told me:
"I was interested in a related problem: in a complete directed graph
with edge weights chosen independently and uniformly from [-x,1-x],
with 0<x<1, what are the statistics on shortest paths? I found that
very little was known, and could not analytically determine the
answers to my questions, and so resorted to simulation."
<ney@camelback.Princeton.edu>
"I've been browsing in this literature almost exclusively for results
on clique and coloring problems, so I'm afraid I can't help much
regarding directed graphs. I recall though Bollobas saying that
probabilistic results on directed graphs were quite scant."
<halldors@paul.rutgers.edu>
The best reference giving some interesting results on distance
properties --- notably diameters and cycles --- for random graphs is:
B\'ela Bollob\'as
Random graphs
Academic Press, 1985
It does not talk about average path length in random graphs, though.
The following book was also suggested, but does not contain what I was
looking for:
Fred Buckley and Frank Harary
Distances in graphs
Addison-Wesley, 1989
I have also browsed through the AMS Mathematical Reviews, but did not
come up with anything directly related to the subject. Most papers study
the bounds on graph diameters or the length of the longest cycle, on the
basis of the number and maximum/minimum degrees of the vertices. For
example:
Mikl\'os Ajtai, Koml\'os J\'anos, and Szemer\'edi Endre
The largest path in a random graph
Combinatorica, 1-1, 1981, pp 1-12
Bill Jackson
Long paths and cycles in oriented graphs
Journal of Graph Theory, 5-2, 1981, pp 145-157
Richard Loulou
Maximal paths in random dynamic graphs
European Journal of Combinatorics, 8-3, 1987, pp 303-311
N. Kusolitsch
On the 1st long path and the number of long paths in certain
directed random graphs
Limit Theorems in Probability and Statistics, I,II, pp 631-647,
Colloquium of the Mathematical Society J\'anos Bolyai no 36,
North-Holland 1982
N. Kusolitsch and T. Nemetz
R\'ev\'esz-Erd\"os-type asymptotic bounds on the length of the
longest path in certain random graphs
Limit Theorems in Probability and Statistics, I,II, pp 649-665,
Colloquium of the Mathematical Society J\'anos Bolyai no 36,
North-Holland 1982
Fan R. K. Cheng
Diameters in graphs: old problems and new results
18th Southeastern International Conference on Combinatorics,
Graph Theory and Computing, Boca Raton, 1987, pp 295-317
There are many more references on related subjects in the mathematical
literature. Needless to say, they are highly theoretical and require a
solid background in mathematics. Anybody interested should consult section
5C of the AMS Reviews to find more about them.
After delving in our library, I have come up with two references that
study the problem of average path length for trees:
Hosam M. Mahmoud
On the average internal path length of m-ary search trees
Acta Informatica, 23-1, 1986, pp 111-117
Rolf Klein and Derick Wood
On the path length of binary trees
JACM, 36-2 April 1986, pp 280-289
I have not tried to launch a full-scale bibliographic search for the
articles and articles on the domain. Somebody deeply involved in the
problem might want to complete the above list of references.
Many thanks to the persons that helped me by providing pointers
and advice:
Chris chris%cs@hub.ucsb.edu
Magnus halldors@paul.rutgers.edu
Kevin McCarty cup.portal.com!kmc@Sun.com@portal.uucp
Neal Young ney@cs.princeton.edu
Eduardo Casais
Centre Universitaire d'Informatique EARN/BITNET: casais@cgeuge51.bitnet
12, rue du Lac EAN/MHS: casais@cuisun.unige.ch
1207 Geneve UUCP: mcsun!cui!casais
SUISSE mcsun!chx400!cui!casais
Telephone: (41) (22) 787.65.86
Telefax: (41) (22) 735.39.05