TR-95-08: Implicit Routing and Shortest Path Information

We study the problem of constructing graphs from shortest path in- formation (complete or partial). Consider graphs with labeled vertices and edges. Given a collection V of vertices and for each u element of V a positive integer d(u), and a family Fu = {Fu,i : i < d(u)} of subsets of V construct a graph such that for each u and each link i of u, Fu;i is the set of nodes having an optimal length path to u passing through link i. In the complete information case we show that a shortest path family uniquely determines the graph and conclude the existence of graphs such that any full information shortest path routing scheme requires a total of (n2) memory bits. We also study the class of unique shortest path graphs”, i.e. graphs for which all vertices are connected by a unique shortest path.