Timeline for Variation on longest path in a DAG
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2013 at 3:30 | comment | added | Neal Young | Ah,with that interpretation of the problem, I agree with your algorithm. | |
| Mar 18, 2013 at 9:11 | comment | added | Magnus Lie Hetland | I guess I misinterpreted the question. I thought you wanted the path with a maximum number of vertices, and then you had some additional constraints, if possible. I guess you meant it the other way around—i.e., among the paths that satisfy your constraints you want the one with the most vertices. If so, sure, my solution doesn't apply :) | |
| Mar 17, 2013 at 15:47 | comment | added | Neal Young | I think Ameer is right -- you can't give the distance complete precedence in your cost function, because you want to find any path with distance at most $d$ (not a path with minimum distance). And if you give the number of vertices on the path precedence, then you might not find a path with length at most $d$, even if one exists. | |
| Mar 17, 2013 at 13:22 | comment | added | AmeerJ | You can't do that. Suppose maximum number of vertices in a path is $V$, and among these paths there is no path with length shorter than $d$. But there is a path with $V-1$ nodes which has a length shorter than $d$ and is the answer. In other words, the number of nodes has not total precedence over the length. | |
| Mar 17, 2013 at 8:14 | history | answered | Magnus Lie Hetland | CC BY-SA 3.0 |