Bibliography

BCH95

J.-C. BERMOND, F. COMELLAS, AND D. HSU, Distributed loop computer networks: A survey, Journal of Parallel and Distributed Computing, 24 (1995), pp. 2-10.

BHV96

H. BUHRMAN, J.-H. HOEPMAN, AND P. VITÁNYI, Optimal routing tables, in 15^th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM PRESS, ed., May 1996, pp. 134-142.

BLTT97

H. L. BODLAENDER, J. V. LEEUWEN, R. B. TAN, AND D. THILIKOS, On interval routing schemes and treewidth, Information and Computation, 139 (1997), pp. 92-109.

Bod92

H. L. BODLAENDER, A tourist guide through treewidth, Tech. Rep. RUU-CS-92-12, Utrecht University, March 1992.
Revised March 1993.

Bra93

V. BRAUME, Theoretische und experimentelle Analyse von Intervall-Routing Algorithmen, PhD thesis, Department of Mathematics and Computer Science, University of Paderborn, 1993.

BvLT91

E. M. BAKKER, J. VAN LEEUWEN, AND R. B. TAN, Linear interval routing, Algorithms Review, 2 (1991), pp. 45-61.

BvLT94

E. M. BAKKER, J. VAN LEEUWEN, AND R. B. TAN.
Unpublished manuscript, 1994.

CDSF98

S. CICERONE, G. DI STEFANO, AND M. FLAMMINI, Static and dynamic low congested interval routing schemes, in 25^th International Colloquium on Automata, Languages and Programming (ICALP), K. Guldstrand Larsen, S. Skyum, and G. Winskel, eds., vol. 1443 of Lecture Notes in Computer Science, Springer, July 1998, pp. 592-603.

dlTNP98

P. DE LA TORRE, L. NARAYANAN, AND D. PELEG, Thy neighbor's interval is greener: A proposal for exploiting interval routing schemes, in 5^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), Carleton Scientific, 1998.

DS87

W. J. DALLY AND C. L. SEITZ, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transaction on Computers, C-36 (1987), pp. 547-553.

Duf65

R. J. DUFFIN, Topology of series parallel graphs, J. Math. Anal. Appl., 10 (1965), pp. 303-318.

EGP98

T. EILAM, C. GAVOILLE, AND D. PELEG, Compact routing schemes with low stretch factor, in 17^th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM PRESS, ed., August 1998, pp. 11-20.

EMZ96

T. EILAM, S. MORAN, AND S. ZAKS, A lower bound for linear interval routing, in 10^th International Workshop on Distributed Algorithms (WDAG), Ö. Babaoglu and K. Marzullo, eds., vol. 1151 of Lecture Notes in Computer Science, Springer-Verlag, October 1996, pp. 191-205.

EMZ97a

T. EILAM, S. MORAN, AND S. ZAKS, The complexity of the characterization of networks supporting shortest-path interval routing, in 4^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), D. Krizanc and P. Widmayer, eds., Carleton Scientific, July 1997, pp. 99-111.

EMZ97b

T. EILAM, S. MORAN, AND S. ZAKS, A simple DFS-based algorithm for linear interval routing, in 11^th International Workshop on Distributed Algorithms (WDAG), M. Mavronicolas and P. Tsigas, eds., vol. 1320 of Lecture Notes in Computer Science, Springer, September 1997, pp. 37-51.

EPTZ97

T. EILAM, D. PELEG, R. B. TAN, AND S. ZAKS, Broadcast in linear messages in IRS representing all shortest paths.
Manuscript, 1997.

FG97

P. FRAIGNIAUD AND C. GAVOILLE, Universal routing schemes, Journal of Distributed Computing, 10 (1997), pp. 65-78.

FG98

P. FRAIGNIAUD AND C. GAVOILLE, Interval routing schemes, Algorithmica, 21 (1998), pp. 155-182.

FGK97

P. FRAIGNIAUD, C. GAVOILLE, AND D. KRIZANC, Communication during the visit of Danny Krizanc at LIP, Ecole Normale Supérieure de Lyon, February 1997.

FGNT98a

M. FLAMMINI, G. GAMBOSI, U. NANNI, AND R. B. TAN, Characterization results of all shortest paths interval routing schemes, in 5^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), L. Gargano and D. Peleg, eds., 1998, pp. 201-213.

FGNT98b

M. FLAMMINI, G. GAMBOSI, U. NANNI, AND R. B. TAN, Multidimensional interval routing schemes, Theoretical Computer Science, 205 (1998), pp. 115-133.

FGS94

M. FLAMMINI, G. GAMBOSI, AND S. SALOMONE, Interval labeling schemes for chordal rings, in 1^st International Colloquium on Structural Information & Communication Complexity (SIROCCO), P. Flocchini, B. Mans, and N. Santoro, eds., Carleton University Press, May 1994, pp. 111-124.

FGS95

M. FLAMMINI, G. GAMBOSI, AND S. SALOMONE, Interval routing schemes, in 12^th Annual Symposium on Theoretical Aspects of Computer Science (STACS), E. W. Mayr and C. Puech, eds., vol. 900 of Lecture Notes in Computer Science, Springer-Verlag, March 1995, pp. 279-290.

FJ88

G. N. FREDERICKSON AND R. JANARDAN, Designing networks with compact routing tables, Algorithmica, 3 (1988), pp. 171-190.

FJ90

G. N. FREDERICKSON AND R. JANARDAN, Space-efficient message routing in c-decomposable networks, SIAM Journal on Computing, 19 (1990), pp. 164-181.

FL96

P. FLOCCHINI AND F. L. LUCCIO, Distance routing on series parallel networks, in 16^th IEEE International Conference on Distributed Computing Systems, March 1996, pp. 352-359.

Fla97a

M. FLAMMINI, Deadlock-free interval routing schemes, in 14^th Annual Symposium on Theoretical Aspects of Computer Science (STACS), R. Reischuk and M. Morvan, eds., vol. 1200 of Lecture Notes in Computer Science, Springer, February 1997, pp. 351-362.

Fla97b

M. FLAMMINI, On the hardness of devising interval routing schemes, Parallel Processing Letters, 7 (1997), pp. 39-47.

FMS97

P. FLOCCHINI, B. MANS, AND N. SANTORO, On the impact of sense of direction on communication complexity, Information Processing Letters, 63 (1997), pp. 23-31.

FMS98a

P. FLOCCHINI, B. MANS, AND N. SANTORO, Sense of direction: Definitions, properties and classes, Networks, 32 (1998), pp. 165-180.

FMS98b

P. FLOCCHINI, B. MANS, AND N. SANTORO, Sense of direction in distributed computing, in 12^th International Symposium on Distributed Computing (DISC), S. Kutten, ed., vol. 1499 of Lecture Notes in Computer Science, Springer, September 1998, pp. 1-15.

FN96

M. FLAMMINI AND E. NARDELLI, On the path length in interval routing schemes.
Manuscript, 1996.

FvLMS95

M. FLAMMINI, J. VAN LEEUWEN, AND A. MARCHETTI-SPACCAMELA, The complexity of interval routing on random graphs, in 20^th International Symposium on Mathematical Foundations of Computer Sciences (MFCS), J. Wiederman and P. Hájek, eds., vol. 969 of Lecture Notes in Computer Science, Springer-Verlag, August 1995, pp. 37-49.

Gav96

C. GAVOILLE, Lower bounds for interval routing on bounded degree networks, Research Report RR-1144-96, LaBRI, University of Bordeaux, 351, cours de la Libération, 33405 Talence Cedex, France, October 1996.

Gav97

C. GAVOILLE, On the dilation of interval routing, in 22^nd International Symposium on Mathematical Foundations of Computer Science (MFCS), I. Prívara and P. Ruzicka, eds., vol. 1300 of Lecture Notes in Computer Science, Springer, August 1997, pp. 259-268.

GG98

C. GAVOILLE AND E. GU´EVREMONT, Worst case bounds for shortest path interval routing, Journal of Algorithms, 27 (1998), pp. 1-25.

GHS83

G. GALLAGER, P. A. HUMBLET, AND P. M. SPIRA, A distributed algorithm for minimal spanning tree, ACM Trans. Programming Languages Systems, 30 (1983), pp. 66-77.

GM97

C. GAVOILLE AND B. MANS, Private communication, August 1997.

Gol80

M. C. GOLUMBIC, Algorithmic Graph Theory and Perfect Graphs, Academic Press, Harcourt Brace Jovanovich, Academic Press ed., 1980.

GP96a

C. GAVOILLE AND S. PSERENN`ES, Lower bounds for interval routing on 3-regular networks, in 3^rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), N. Santoro and P. Spirakis, eds., Carleton University Press, June 1996, pp. 88-103.

GP96b

C. GAVOILLE AND S. PSERENN`ES, Memory requirement for routing in distributed networks, in 15^th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM PRESS, ed., May 1996, pp. 125-133.

GP97

C. GAVOILLE AND D. PELEG, The compactness of interval routing, Research Report RR-1176-97, LaBRI, University of Bordeaux, 351, cours de la Libération, 33405 Talence Cedex, France, September 1997.

GP98

C. GAVOILLE AND D. PELEG, The compactness of interval routing for almost all graphs, in 12^th International Symposium on Distributed Computing (DISC), S. Kutten, ed., vol. 1499 of Lecture Notes in Computer Science, Springer, September 1998, pp. 161-174.

GV96

G. GAMBOSI AND P. VOCCA, Topological routing schemes, in 10^th International Workshop on Distributed Algorithms (WDAG), Ö. Babaoglu and K. Marzullo, eds., vol. 1151 of Lecture Notes in Computer Science, Springer-Verlag, October 1996, pp. 206-219.

Hal86

M. J. HALL, Combinatorial Theory (second edition), Wiley-Interscience Publication, 1986.

HKR91

H. HOFEST¨ADT, A. KLEIN, AND E. REYZL, Performance benefits from locally adaptative interval routing in dynamically switched interconnection networks, in Distributed Memory Computing: 2^nd European Conference, EDMCC2, A. Bode, ed., vol. 487 of Lecture Notes in Computer Science, Munich, April 1991, Springer-Verlag, pp. 193-202.

HMS89

M.-C. HEYDEMANN, J. MEYER, AND D. SOTTEAU, On forwarding indices of networks, Discrete Applied Mathematics, 23 (1989), pp. 103-123.

Jug93

M. JUGANARU, Routage avec table de routage compacte, stage de DEA, ENSIMAG, Grenoble, June 1993.

KK96

E. KRANAKIS AND D. KRIZANC, Lower bounds for compact routing, in 13^th Annual Symposium on Theoretical Aspects of Computer Science (STACS), C. Puech and R. Reischuk, eds., vol. 1046 of Lecture Notes in Computer Science, Springer-Verlag, February 1996, pp. 529-540.

KKR93

E. KRANAKIS, D. KRIZANC, AND S. S. RAVI, On multi-label linear interval routing schemes, in 19^th International Workshop on Graph - Theoretic Concepts in Computer Science - Distributed Algorithms (WG), vol. 790 of Lecture Notes in Computer Science, Springer-Verlag, June 1993, pp. 338-349.

KL95

D. KRIZANC AND F. L. LUCCIO, Boolean routing on chordal rings, in 2^nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), L. M. Kirousis and E. Kranakis, eds., Carleton University Press, June 1995, pp. 89-100.

Klo94

T. KLOKS, Treewidth: Computations and Approximations, vol. 842 of Lectures Notes in Computer Science, Springer-Verlag, June 1994.

KRRS98

R. KRÁSLOVISC, B. ROVAN, P. RUSZISCKA, AND D. STEFANKOVISC, Efficient deadlock-free multi-dimensional interval routing in interconnection networks, in 12^th International Symposium on Distributed Computing (DISC), S. Kutten, ed., vol. 1499 of Lectures Notes in Computer Science, Springer, September 1998, pp. 273-287.

KRS97a

R. KRÁSLOVISC, P. RUSZISCKA, AND D. STEFANKOVISC, The complexity of shortest path and dilation bounded interval routing, in 3^rd International Euro-Par Conference, C. Lengaur, M. Griebl, and S. Gorlatch, eds., vol. 1300 of Lectures Notes in Computer Science, Springer, August 1997, pp. 258-265.

KRS97b

R. KRÁSLOVISC, P. RUSZISCKA, AND D. STEFANKOVISC, The complexity of shortest path and dilation bounded interval routing.
Manuscript to appear in TCS, full version of [KRS97a], 1997.

LV93

M. LI AND P. M. B. VIT´ANYI, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, 1993.

LW96

P. LOH AND J. WENGE, Adaptive, fault-tolerant, deadlock-free and livelock-free interval routing in mesh networks, in 2^nd IEEE International Conference on Algorithms & Architectures for Parallel Processing (ICAPP), June 1996, pp. 348-355.

Man98

B. MANS, On the interval routing of chordal rings of degree 4, Tech. Rep. C/TR98-09, Macquarie University, Dept. of Computing, School of MPCE, Macquarie University, Sydney NSW2109, Australia, July 1998.

MT90

D. MAY AND P. THOMPSON, Transputers and routers: Components for concurrent machines, INMOS Ltd., (1990).

NN96

L. NARAYANAN AND N. NISHIMURA, Interval routing on k-trees, in 3^rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), N. Santoro and P. Spirakis, eds., Carleton University Press, June 1996, pp. 104-118.

NO97

L. NARAYANAN AND J. OPATRNY, Compact routing on chordal rings of degree four, in 4^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), D. Krizanc and P. Widmayer, eds., Carleton Scientific, July 1997, pp. 125-137.

NS96

L. NARAYANAN AND S. SHENDE, Characterizations of networks supporting shortest-path interval labeling schemes, in 3^rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), N. Santoro and P. Spirakis, eds., Carleton University Press, June 1996, pp. 73-87.

PU88

D. PELEG AND E. UPFAL, A trade-off between space and efficiency for routing tables, in 20^th Annual ACM Symposium on Theory of Computing (STOC), Chicago, IL, May 1988, pp. 43-52.

RS97

P. RUSZISCKA AND D. STEFANKOVISC, On the complexity of multi-dimensional interval routing schemes.
Submitted to TCS, September 1997.

Ruz88

P. RUZISCKA, On efficiency of interval routing algorithms, in 13^rd International Symposium on Mathematical Foundations of Computer Science (MFCS), M. Chytil, L. Janiga, and V. Koubek, eds., vol. 324 of Lectures Notes in Computer Science, Springer-Verlag, 1988, pp. 492-500.

Sch97

H. SCHOMBERG, Chord and shuffle augmented mesh topologies for messages-passing multicomputers.
Manuscript, 1997.

SK82

N. SANTORO AND R. KHATIB, Routing without routing tables, Tech. Rep. SCS-TR-6, School of Computer Science, Carleton University, Ottawa, 1982.

SK85

N. SANTORO AND R. KHATIB, Labelling and implicit routing in networks, The Computer Journal, 28 (1985), pp. 5-8.

SML94

I. SAKHO, L. MUGWANEZA, AND Y. LANGUE, Routing with compact tables: interval labelling scheme for generalized meshes, in IFIP Transactions: Applications in Parallel and Distributed Computing (APDC), C. Girault, ed., Elsevier Science B.V. (North-Holland), 1994, pp. 297-308.

SRS97

SIENA RESEARCH SCHOOL, Communication at the Siena Research School '97 on ``Compact Routing and Sense of Direction'', June 1997.

Tel94

G. TEL, Introduction to Distributed Algorithms, Cambridge University Press, 1994.

TL95

S. S. H. TSE AND F. C. M. LAU, Lower bounds for multi-label interval routing, in 2^nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), L. M. Kirousis and E. Kranakis, eds., Carleton University Press, June 1995, pp. 123-134.

TL97a

S. S. H. TSE AND F. C. M. LAU, A lower bound for interval routing in general networks, Networks, 29 (1997), pp. 49-53.

TL97b

S. S. H. TSE AND F. C. M. LAU, An optimal lower bound for interval routing in general networks, in 4^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), D. Krizanc and P. Widmayer, eds., Carleton Scientific, July 1997, pp. 112-124.

TL97c

S. S. H. TSE AND F. C. M. LAU, Some lower-bound results on interval routing in planar graphs, Tech. Rep. TR-97-05, Department of Computer Science, The University of Hong Kong, April 1997.

VDLP94

J. VOUNCKX, G. DECONINCK, R. LAUWEREINS, AND J. A. PEPERSTRAETE, Fault-tolerant compact routing based on reduced structural information in wormhole-switching based networks, in 1^st International Colloquium on Structural Information & Communication Complexity (SIROCCO), P. Flocchini, B. Mans, and N. Santoro, eds., Carleton University Press, May 1994, pp. 125-147.

vLT83

J. VAN LEEUWEN AND R. B. TAN, Routing with compact routing tables, Tech. Rep. RUU-CS-83-16, Department of Computer Science, University of Utrecht, Utrecht, November 1983.

vLT86

J. VAN LEEUWEN AND R. B. TAN, Computer networks with compact routing tables, in The Book of L, G. Rozemberg and A. Salomaa, eds., Springer-Verlag, 1986, pp. 259-273.

vLT87

J. VAN LEEUWEN AND R. B. TAN, Interval routing, The Computer Journal, 30 (1987), pp. 298-307.

vLT94

J. VAN LEEUWEN AND R. B. TAN, Compact routing methods: A survey, in 1^st International Colloquium on Structural Information & Communication Complexity (SIROCCO), P. Flocchini, B. Mans, and N. Santoro, eds., Carleton University Press, May 1994, pp. 99-110.

ZBG94

B. ZERROUK, J. BLIN, AND A. GREINER, Encapsuling networks and routing, in 8^th International Parallel Processing Symposium (IPPS), 1994, pp. 546-553.

Zem97

A. ZEMMARI, Routage compact et adaptatif, rapport de stage de DEA, Université de Bordeaux, 351 cours de la Libération, 33405 Talence cedex, France, June 1997.
"http://www.labri.u-bordeaux.fr/~gavoille/article/Zemmari97.p s.gz". An english version is in preparation.

ZRP$^$96

B. ZERROUK, V. REIBALDI, F. POTTER, A. GREINER, AND D. ANNE, Rcube: A gigabit serial links low latency adaptive router, in the Records of the IEEE Hot Interconnects IV, Palo Alto CA, U.S.A, August 1996.

ZTRP94

B. ZERROUK, S. TRICOT, B. ROTTEMBOURG, AND L. PATNAIK, Proper linear interval routing schemes, Tech. Rep. N94-29, IBP-MASI, October 1994.