Next: Contents
Up: A Survey on Interval
Previous: Interval Routing for Distributed
Contents
 BCH95

J.C. BERMOND, F. COMELLAS, AND D. HSU, Distributed loop computer
networks: A survey, Journal of Parallel and Distributed Computing, 24
(1995), pp. 210.
 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. 134142.
 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. 92109.
 Bod92

H. L. BODLAENDER, A tourist guide through treewidth, Tech. Rep.
RUUCS9212, Utrecht University, March 1992.
Revised March 1993.
 Bra93

V. BRAUME, Theoretische und experimentelle Analyse von
IntervallRouting 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. 4561.
 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. 592603.
 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, Deadlockfree message routing in
multiprocessor interconnection networks, IEEE Transaction on Computers, C36
(1987), pp. 547553.
 Duf65

R. J. DUFFIN, Topology of series parallel graphs, J. Math. Anal.
Appl., 10 (1965), pp. 303318.
 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. 1120.
 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, SpringerVerlag, October 1996, pp. 191205.
 EMZ97a

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

T. EILAM, S. MORAN, AND S. ZAKS, A simple DFSbased 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. 3751.
 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. 6578.
 FG98

P. FRAIGNIAUD AND C. GAVOILLE, Interval routing schemes,
Algorithmica, 21 (1998), pp. 155182.
 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. 201213.
 FGNT98b

M. FLAMMINI, G. GAMBOSI, U. NANNI, AND R. B. TAN, Multidimensional
interval routing schemes, Theoretical Computer Science, 205 (1998),
pp. 115133.
 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. 111124.
 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, SpringerVerlag, March 1995, pp. 279290.
 FJ88

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

G. N. FREDERICKSON AND R. JANARDAN, Spaceefficient message routing
in cdecomposable networks, SIAM Journal on Computing, 19 (1990),
pp. 164181.
 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. 352359.
 Fla97a

M. FLAMMINI, Deadlockfree 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. 351362.
 Fla97b

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

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

P. FLOCCHINI, B. MANS, AND N. SANTORO, Sense of direction:
Definitions, properties and classes, Networks, 32 (1998), pp. 165180.
 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. 115.
 FN96

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

M. FLAMMINI, J. VAN LEEUWEN, AND A. MARCHETTISPACCAMELA, 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, SpringerVerlag, August 1995, pp. 3749.
 Gav96

C. GAVOILLE, Lower bounds for interval routing on bounded degree
networks, Research Report RR114496, 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. 259268.
 GG98

C. GAVOILLE AND E. GU´EVREMONT, Worst case bounds for shortest
path interval routing, Journal of Algorithms, 27 (1998), pp. 125.
 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. 6677.
 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 3regular networks, in 3^{rd} International Colloquium on
Structural Information & Communication Complexity (SIROCCO), N. Santoro and
P. Spirakis, eds., Carleton University Press, June 1996, pp. 88103.
 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. 125133.
 GP97

C. GAVOILLE AND D. PELEG, The compactness of interval routing,
Research Report RR117697, 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. 161174.
 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, SpringerVerlag, October 1996, pp. 206219.
 Hal86

M. J. HALL, Combinatorial Theory (second edition),
WileyInterscience 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, SpringerVerlag, pp. 193202.
 HMS89

M.C. HEYDEMANN, J. MEYER, AND D. SOTTEAU, On forwarding indices of
networks, Discrete Applied Mathematics, 23 (1989), pp. 103123.
 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, SpringerVerlag, February 1996, pp. 529540.
 KKR93

E. KRANAKIS, D. KRIZANC, AND S. S. RAVI, On multilabel 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, SpringerVerlag, June 1993,
pp. 338349.
 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. 89100.
 Klo94

T. KLOKS, Treewidth: Computations and Approximations, vol. 842 of
Lectures Notes in Computer Science, SpringerVerlag, June 1994.
 KRRS98

R. KRÁSLOVISC, B. ROVAN, P. RUSZISCKA, AND
D. STEFANKOVISC, Efficient deadlockfree multidimensional
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. 273287.
 KRS97a

R. KRÁSLOVISC, P. RUSZISCKA, AND D. STEFANKOVISC,
The complexity of shortest path and dilation bounded interval routing,
in 3^{rd} International EuroPar Conference, C. Lengaur, M. Griebl, and
S. Gorlatch, eds., vol. 1300 of Lectures Notes in Computer Science, Springer,
August 1997, pp. 258265.
 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, SpringerVerlag, 1993.
 LW96

P. LOH AND J. WENGE, Adaptive, faulttolerant, deadlockfree and
livelockfree interval routing in mesh networks, in 2^{nd} IEEE
International Conference on Algorithms & Architectures for Parallel
Processing (ICAPP), June 1996, pp. 348355.
 Man98

B. MANS, On the interval routing of chordal rings of degree 4,
Tech. Rep. C/TR9809, 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 ktrees, in
3^{rd} International Colloquium on Structural Information & Communication
Complexity (SIROCCO), N. Santoro and P. Spirakis, eds., Carleton University
Press, June 1996, pp. 104118.
 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. 125137.
 NS96

L. NARAYANAN AND S. SHENDE, Characterizations of networks supporting
shortestpath 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. 7387.
 PU88

D. PELEG AND E. UPFAL, A tradeoff between space and efficiency for
routing tables, in 20^{th} Annual ACM Symposium on Theory of Computing
(STOC), Chicago, IL, May 1988, pp. 4352.
 RS97

P. RUSZISCKA AND D. STEFANKOVISC, On the complexity
of multidimensional 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, SpringerVerlag, 1988, pp. 492500.
 Sch97

H. SCHOMBERG, Chord and shuffle augmented mesh topologies for
messagespassing multicomputers.
Manuscript, 1997.
 SK82

N. SANTORO AND R. KHATIB, Routing without routing tables, Tech.
Rep. SCSTR6, 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. 58.
 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. (NorthHolland), 1994, pp. 297308.
 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 multilabel 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. 123134.
 TL97a

S. S. H. TSE AND F. C. M. LAU, A lower bound for interval routing in
general networks, Networks, 29 (1997), pp. 4953.
 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. 112124.
 TL97c

S. S. H. TSE AND F. C. M. LAU, Some lowerbound results on interval
routing in planar graphs, Tech. Rep. TR9705, Department of Computer
Science, The University of Hong Kong, April 1997.
 VDLP94

J. VOUNCKX, G. DECONINCK, R. LAUWEREINS, AND J. A. PEPERSTRAETE, Faulttolerant compact routing based on reduced structural information in
wormholeswitching 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. 125147.
 vLT83

J. VAN LEEUWEN AND R. B. TAN, Routing with compact routing tables,
Tech. Rep. RUUCS8316, 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.,
SpringerVerlag, 1986, pp. 259273.
 vLT87

J. VAN LEEUWEN AND R. B. TAN, Interval routing, The Computer
Journal, 30 (1987), pp. 298307.
 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. 99110.
 ZBG94

B. ZERROUK, J. BLIN, AND A. GREINER, Encapsuling networks and
routing, in 8^{th} International Parallel Processing Symposium (IPPS),
1994, pp. 546553.
 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.ubordeaux.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. N9429, IBPMASI, October 1994.
20000321