Designing networks with compact routing tables

Greg N. Frederickson, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

106 Scopus citations


Classes of network topologies are identified in which shortest-path information can be succinctly stored at the nodes, if they are assigned suitable names. The naming allows each edge at a node to be labeled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy of networks is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.

Original languageEnglish (US)
Pages (from-to)171-190
Number of pages20
JournalAlgorithmica (New York)
Issue number1
StatePublished - 1988


Dive into the research topics of 'Designing networks with compact routing tables'. Together they form a unique fingerprint.

Cite this