Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
The Symmetric Shortest-Path Table Routing Conjecture

Thomas L. Rodeheffer


A symmetric shortest-path table routing is a set of paths between all pairs of nodes in a graph such that the set is closed under path reversal, each path is a shortest path in the graph, and all paths with the same destination form a tree with a sink at the destination. Such a routing can be found for any finite, connected, undirected, positive-weighted graph by “salting” the edge weights so that all the shortest salted paths are unique while each one remains a shortest path in the original graph. A conjecture arises about whether every possible symmetric shortest-path table routing can be selected in this way by some edge weight salting. It turns out that this conjecture is false. This paper describes the search for counterexamples.


Publication typeTechReport
PublisherMicrosoft Technical Report
> Publications > The Symmetric Shortest-Path Table Routing Conjecture