Timeline for Graph-theoretic algorithm for path with minimum average edge length
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2020 at 15:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 29, 2020 at 14:25 | history | edited | YCor | CC BY-SA 4.0 |
formatting
|
| Nov 29, 2020 at 14:13 | answer | added | Manfred Weis | timeline score: 1 | |
| Apr 28, 2018 at 12:00 | comment | added | Max Alekseyev | Non-simple paths do not pose a trouble for dynamic programming in this case (since it looks for paths with fixed number of edges). The trouble may come from existence of short cycles, which may need to be taken infinitely many times along a path from $a$ to $b$ to get the average edge length down to the minimum. So, besides finding finite paths, one has to explore cycles to determine whether the minimum is achieved on infinite paths. | |
| Apr 28, 2018 at 6:40 | comment | added | Manfred Weis | @MaxAlekseyev dynamic programming would have been an option, if simplicity of the reported paths were guaranteed. It is however an option to filter out all non-simple paths to find an upper bound on the optimal solution. | |
| Apr 27, 2018 at 22:01 | comment | added | Max Alekseyev | Using dynamic programming, one can find a shortest path between $a$ and $b$ with a fixed number of edges $k$ (for all values of $k$). It remain to divide the length of each such path by the corresponding $k$, and pick the one with the smallest ratio. | |
| Apr 27, 2018 at 18:34 | history | asked | Manfred Weis | CC BY-SA 3.0 |