{"id":12772,"date":"2021-11-20T18:56:18","date_gmt":"2021-11-20T23:56:18","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12772"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-95-08-implicit-routing-and-shortest-path-information","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-08-implicit-routing-and-shortest-path-information\/","title":{"rendered":"TR-95-08: Implicit Routing and Shortest Path Information"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-95-08: Implicit Routing and Shortest Path Information\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-95-08
\nApril 1995<\/p>\n\n\n\n

Implicit Routing and Shortest Path Information<\/h2>\n\n\n\n
\n
\n
\n
\n
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
\n

Abstract<\/h3>\n<\/div>\n\n\n\n
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.<\/div>\n\n\n\n

TR-95-08.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-08 April 1995 Implicit Routing and Shortest Path Information Evangelos Kranakis, Danny Krizanc, Jorge Urrutia Abstract 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12772","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12772"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12772\/revisions"}],"predecessor-version":[{"id":12773,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12772\/revisions\/12773"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12772"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}