Partial characterizations of networks supporting shortest path interval labeling schemes

作     者：Narayanan, L Shende, S 

作者机构：Concordia Univ Dept Comp Sci Montreal PQ H3G 1M8 Canada Univ Nebraska Dept Comp Sci & Engn Lincoln NE 68588 USA 

出 版 物：《NETWORKS》 (网络)

年 卷 期：1998年第32卷第2期

页      面：103-113页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：theory of parallel and distributed computation interval routing algorithms graph theory 

摘      要：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 greater than or equal to 1 subintervals per edge is closed under composition with a certain class of graphs. (C) 1998 John Wiley & Sons, Inc.