0
$\begingroup$

This problem is analogous to fast removal of the minimum number of edges in a weighted graph such that if the graph were to be drawn on paper with edge lengths linear in proportion to their weights, it could be drawn with only line segments (and perhaps dots for vertices or some other aesthetically pleasing touch)
I have come up with a simple and naive solution of using the previous research on fast apsp algorithms to my advantage (all pairs shortest paths). This runs in n^2 expected time with high probability as shown by B. Sudakov (in the most prominent and recent paper I could find while browsing google scholar) Once the edges that exist in the shortest paths are found, the others can be ignored.
But this problem is not that hard! I don't need to actually know the paths, I just need to know every edge that isn't or equivalently is present. Or is it? I'll take anything from a full blown algorithm to a proof detailing a better time bound. Note that the paper I'm referencing above delivers an expected time bound and worst-case is what I care most about right now.

$\endgroup$
2
  • 2
    $\begingroup$ I don't know exactly what you mean by $n^2$ expected time, what is the random model? But it seems you want to keep only the edges that are in themselves the shortest path between their two endpoints, because those are precisely the ones that occur in some shortest path, right? One idea is to find a spanning tree (for instance consisting of all shortest paths from one particular vertex) and start by discarding all edges that are longer than the diameter of that tree. Then look more carefully at what's left. $\endgroup$ Jun 14, 2011 at 11:36
  • $\begingroup$ So is this equivalent to computing all-pairs shortest path, then deleting all edges not contained in some shortest path? And I don't really understand the question... use the Floyd-Warshall algorithm if you want it to be simple, and use this Sudakov result you mention if you want it to be fast. I highly doubt that you would easily be able to construct the edge set faster than that, but I may be wrong. $\endgroup$ Jun 15, 2011 at 11:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.