Implicit Routing and Shortest Path Information (Extended Abstract).
Evangelos Kranakis, Danny Kriz̧anc, Jorge Urrutia · 1995
We study the problem of constructing graphs from shortest path information (complete or partial). Consider graphs with labeled vertices and edges. Given a collection V of vertices and for each u 2 V a positive integer d(u), and a family F u = fF u;i : i ! d(u)g of subsets of V construct a graph such that for each u and each link i of u, F u;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 \\Omega\\Gamma n²) 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.