Partial characterizations of networks supporting shortest path interval labeling schemes

✍ Scribed by Narayanan, Lata; Shende, Sunil

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 159 KB
• Volume: 32
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199809)32:2<103::aid-net3>3.0.co;2-f

✦ Synopsis

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.