This paper presents a routing strategy called Pivot Inter-val Routing (PIR), which allows
inessage routing on every weighted n-node network along paths whose stretch (namely, the …

This survey concerns the role of data structures for compactly storing and representing
various types of information in a localized and distributed fashion. Traditional approaches to …

This book presents the history and state of the art of universal routing strategies, which can
be applied to networks independently of their respective topologies. It opens with a self …

We survey in this paper the classical results, and also the most recent results, in the field of
Interval Routing, a well-known strategy to code in a compact way distributed routing …

A chordal ring G (n; c) of degree 4 is a ring of n nodes with chords connecting each vertex i
to the vertex (i+ c) mod n. In this paper we investigate compact routing schemes on such …

The compactness of a graph measures the space complexity of its shortest path routing
tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses …

A subset of nodes S in a graph G is called k-dominating if, for every node u of the graph, the
distance from u to S is at most k. We consider the parameter γ k (G) defined as the cardinality …

Interval routing is an attractive space-efficient routing method for point-to-point
communication networks which found industrial applications in novel transputer routing …

Interval routing is a space-efficient (compact) routing method for point-topoint
communication networks. The method is based on proper labeling of edges of the graph …

In this paper we deal with interval routing on n-node networks of diameter D. We show that
for every fixed D≥ 2, there exists a network on which every interval routing scheme with O …