𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of shortest path and dilation bounded interval routing

✍ Scribed by Rastislav Kráľovič; Peter Ružička; Daniel Štefankovič

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
227 KB
Volume
234
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Interval routing is a popular compact routing method for point-to-point networks which found industrial applications in novel transputer routing technology (May and Thompson, Transputers and Routers: Components for Concurrent Machines, Inmos, 1991).

Recently much e ort is devoted to relate the e ciency (measured by the dilation or the stretch factor) to space requirements (measured by the compactness or the total number of memory bits) in a variety of compact routing methods (Eilam,

📜 SIMILAR VOLUMES

The time-dependent shortest pair of disj
The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 3 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu

Upper and lower bounds for the average-c
Upper and lower bounds for the average-case complexity of path-search
✍ Pippenger, Nicholas 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent