Timeline for length of paths between two nodes in a directed acyclic graph
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 25, 2012 at 14:28 | comment | added | Brendan McKay | When I wrote $O(mn)$ and $O(n^2)$, I must have been thinking about paths from a fixed vertex to each other vertex. Sorry about that. If all pairs of vertices are required, I think $O(n^3)$ output might be needed (unless there is a compressed way of expressing the answer), and $O(n^2m)$ is what dynamic programming does. | |
| Jun 27, 2012 at 18:42 | comment | added | user24732 | 1. It's not a home work question, most universities are closed now :-) 2. It's complexity should not be O(n^2), as for each pair of vertices, we can have more than one path, hence, more than one path lengths. The complexity is O(nm). However, I will look into this. Though I was looking for a combinatorial formula, it seems that might not be possible. 3. The matrix multiplication process does it in O(n^4), assuming standard matrix multiplication algorithm. | |
| Jun 27, 2012 at 4:31 | comment | added | Brendan McKay | @Hugh: an algorithms course. The standard algorithm for shortest paths in acyclic digraphs (which is a generalization of most textbook examples of dynamic programming, such as longest common substring) is easily adapted. For $n$ vertices and $m$ edges, it is easy to do it in time $O(mn)$. A lower bound is $n^2$ since that is how large the answer can be, but at the moment I don't see how to do it that fast. | |
| Jun 27, 2012 at 1:21 | comment | added | Hugh Denoncourt | That did not occur to me, though it does now. What kind of course would it be an exercise in? | |
| Jun 27, 2012 at 1:14 | comment | added | Brendan McKay | This is an easy dynamic programming exercise. Is it homework? | |
| Jun 27, 2012 at 1:09 | answer | added | Hugh Denoncourt | timeline score: 2 | |
| Jun 27, 2012 at 0:17 | comment | added | user24732 | suppose a and b are two vertices in a DAG (V,E). There are m paths between A and B. What is the best way to determine length of each of m paths from a to b? I need to do this for all pairs (a,b) that belongs to V. | |
| Jun 26, 2012 at 21:27 | comment | added | Chris Godsil | It's not clear what you are asking for. Do you want to determine the set of possible lengths of paths from one vertex to another? | |
| Jun 26, 2012 at 21:23 | history | asked | user24732 | CC BY-SA 3.0 |