The Symmetric Shortest-Path Table Routing Conjecture

Thomas L. Rodeheffer

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2013-58
PublisherMicrosoft Technical Report
> Publications > The Symmetric Shortest-Path Table Routing Conjecture