Timeline for Variation on longest path in a DAG
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2013 at 14:32 | answer | added | AmeerJ | timeline score: 1 | |
| Mar 17, 2013 at 8:14 | answer | added | Magnus Lie Hetland | timeline score: 0 | |
| Mar 17, 2013 at 2:48 | comment | added | Neal Young | When you say distance remaining, what precisely do you mean? Do you mean the length of the shortest path (from where you are to $e$) (i) in the original graph or (ii) along the chosen path? (I read it as the latter, which doesn't make sense to me, because the distances will be decreasing along any path.) If you mean the former, isn't the problem easy? Just delete all edges $(u,w)$ such that distance$(u,e)<$distance$(w,e)$, then find the longest path (meaning, path with the most edges) in the resulting DAG using the standard dynamic programming algorithm for longest path in a DAG. | |
| Mar 16, 2013 at 22:41 | history | tweeted | twitter.com/#!/StackCSTheory/status/313057361973616640 | ||
| Mar 15, 2013 at 10:51 | comment | added | Jiyda Moussa | @Neal Young, Closer means that as you go through the path you reduce the distance remaining between you and your destination. Do you know the name of this problem? | |
| Mar 15, 2013 at 3:25 | comment | added | Neal Young | Can you clarify what you mean in (2) by "closer"? It reads as if you mean with respect to distance along the chosen path, but choosing any simple path would give you that property, I think, so it doesn't quite make sense. In any case, isn't this an easy dynamic programming exercise? | |
| Mar 15, 2013 at 2:30 | history | edited | Tyson Williams | CC BY-SA 3.0 |
LaTeXed math and improved wording
|
| Mar 15, 2013 at 2:10 | review | First posts | |||
| Mar 15, 2013 at 13:47 | |||||
| Mar 15, 2013 at 1:50 | history | asked | Jiyda Moussa | CC BY-SA 3.0 |