Timeline for Reference Request: designing a tree of "main roads" in a graph
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2017 at 9:04 | comment | added | Lwins | Thanks for your patient explanation. While I still think there is some problem. My opinion is when $n=2$ or equivalently $T$ has only one edge, your algorithm is correct. But maybe we will meet some trouble when $n$ is large. Using your algorithm I could not get the best solution $ABCD$ in the OP. | |
| Sep 27, 2017 at 8:56 | comment | added | Manfred Weis | The basic idea is, that it brings most to replace edges where the product of weight and number of shortest paths they are on, bring the biggest gain when replacing their weight by 0, because all shortest paths that contain that edge will also contain it after its weight has been set to zero. The Kruskal algorithm grows trees in parallel and therefore allows one to find the heaviest subtree. Setting the edges of the heaviest subtree of size $n$ to 0 is the heuristic for the biggest decrease of summed shortest paths lengths. | |
| Sep 27, 2017 at 7:43 | comment | added | Lwins | I could not understand to some extent. Would you be so kind to show how your algorithm succeeds on the case in my post? | |
| Sep 27, 2017 at 7:38 | comment | added | Manfred Weis | @Lwins that doesn't harm the algorithm; the new shortest paths may use an arbitrary number of the tree edges instead of shortcutting between two tree-vertices; I took that into account in my algorithm. | |
| Sep 27, 2017 at 6:21 | comment | added | Lwins | I think maybe there is some problem in it. We can not guarantee that if a path is not a shortest path in $G$, it will not appear in the final scheme. | |
| Sep 27, 2017 at 5:43 | history | answered | Manfred Weis | CC BY-SA 3.0 |