The Symmetric Shortest-Path Table Routing Conjecture

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.

paper.pdf
PDF file

Publisher  Microsoft Technical Report
Copyright (c) 2013 Microsoft Corporation.

Details

TypeTechReport
NumberMSR-TR-2013-58
> Publications > The Symmetric Shortest-Path Table Routing Conjecture