From: gwoegi@fmatbds01.tu-graz.ac.REMOVE.at (Gerhard J. Woeginger)
Subject: Re: estimate for number of paths
Date: Tue, 28 Sep 1999 11:21:54
Newsgroups: comp.theory,sci.math
Keywords: paths in acyclic digraphs

In article <7snccc$h6m$1@cnn.cc.biu.ac.il> yuvalk@sunlight.cs.biu.ac.il (Yuval Krymolowski) writes:
From: yuvalk@sunlight.cs.biu.ac.il (Yuval Krymolowski)
>Subject: estimate for number of paths
>Date: 27 Sep 1999 09:11:40 GMT

> Given a directed a-cyclic graph, I would like to estimate
> the number of paths between two vertices.

> Could someone please provide me with reference to a
> related work ?

>  Thanks,
>     Yuval Krymolowski
>     Bar-Ilan University

In acyclic graphs, this number can be computed exactly in polynomial time, by 
dynamic programming: Sort the vertices topologically, and call the resulting 
numbering 1,2,...,n. W.l.o.g. we want to compute the number of paths from the 
source vertex 1 to the sink vertex n.  
Denote by P[j] the number of distinct paths that start in 1 and end in j; such 
a path can only use vertices with numbers between 1 and j.  Then you get
   P[1] = 1
   P[j] = \sum_{ (k,j) in E } P[k]

- Gerhard
___________________________________________________________
Gerhard J. Woeginger  (gwoegi@opt.math.tu-graz.ac.at)