Partial characterizations of networks supporting shortest path interval labeling schemes

Lata Narayanan, Sunil Shende

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


In this paper, we consider the problem of shortest path interval routing, a space-efficient strategy for routing in distributed networks. In this scheme, an ordering of the vertices is chosen so that the edges of the network can be labeled with one or more subintervals of the vertex ordering: The resulting routing tables must be deterministic and route along shortest paths between all pairs of vertices. We first show constructively that any interval graph can be labeled with one circular subinterval on each edge; this extends a known result for proper interval graphs. We also provide a partial characterization for networks that admit linear interval routing when edges are labeled with exactly one interval, in terms of the biconnected components of any such network. This is the first such characterization when the paths are required to be shortest paths under the distance metric. Finally, we show that the class of networks that can be labeled with k ≥ 1 subintervals per edge is closed under composition with a certain class of graphs.

Original languageEnglish (US)
Pages (from-to)103-113
Number of pages11
Issue number2
StatePublished - Sep 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


  • Graph theory
  • Interval routing algorithms
  • Theory of parallel and distributed computation


Dive into the research topics of 'Partial characterizations of networks supporting shortest path interval labeling schemes'. Together they form a unique fingerprint.

Cite this