Skip Navigation

The Computer Journal 1998 41(1):16-25; doi:10.1093/comjnl/41.1.16
© 1998 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (9)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Flammini, M.
Right arrow Articles by Marchetti-Spaccamela, A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

The Complexity of Interval Routing on Random Graphs

M. Flammini1, J. van Leeuwen2 and A. Marchetti-Spaccamela3

1 Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, via Vetoio loc. Coppito, I-67100 l'Aquila, Italy Email: flammini{at}univaq.it, 2 Department of Computer Science, Utrecht University, Padualaan 14, 3584 CH Utrecht, The Netherlands, 3 Dipartimento di Informatica e Sistemistica, University of Rome ‘La Sapienza’, via Salaria 113, I-00198 Rome, Italy

Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schemes (k-IRS), links carry up to k intervals each. A message is routed over a certain link if its destination belongs to one of the intervals of the link. We present some results for the necessary value of k in order to achieve shortest-path routing. Even though low values of k suffice for very structured networks, we show that for ‘general graphs’ interval routing cannot significantly reduce the space requirements for shortest-path routing. In particular we show that for suitably large n, there are suitable values of p such that for randomly chosen graphs G Gn, p the following holds, with high probability: if G admits an optimal k-IRS, then

[equation: see PDF]

. The result is obtained by means of a novel matrix representation for the shortest paths in a network.

Received October 3, 1996. revised January 21, 1998.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.