1

Y. AFEK, E. GAFNI, AND M. RICKLIN, Upper and lower bounds for routing schemes in dynamic networks, in 30th Annual Symposium on Foundations of Computer Science (FOCS); IEEE Computer Society Press, Oct. 1989, pp. 370-375.

2

Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada  [doi>10.1145/135419.135430]

3

Alfred V. Aho, Algorithms for finding patterns in strings, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

4

B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States  [doi>10.1145/73007.73053]

5

B. AWERBUCH, Y. MANSOUR, AND N. SHAVIT, Polynomial end-to-end communication, in 30th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Oct. 1989, pp. 358-363.

6

B. AWERBUCH AND D. PELEG, Sparse partitions, in 31th Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1990, pp. 503-513.

7

B. BOLLOBÁS, Random Graphs, Academic Press, New York, 1975.

8

Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Almost-Minimum Space, SIAM Journal on Computing, v.28 n.5, p.1627-1640, April/May 1999  [doi>10.1137/S0097539795294165]

9

Harry Buhrman , Jaap-Henk Hoepman , Paul Vitányi, Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method, SIAM Journal on Computing, v.28 n.4, p.1414-1432, Aug. 1999  [doi>10.1137/S0097539796308485]

10

Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.255-260, January 17-19, 1999, Baltimore, Maryland, United States

11

Shlomi Dolev , Evangelos Kranakis , Danny Krizanc , David Peleg, Bubbles: adaptive routing scheme for high-speed dynamic networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.528-537, May 29-June 01, 1995, Las Vegas, Nevada, United States  [doi>10.1145/225058.225270]

12

Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico  [doi>10.1145/277697.277702]

13

Michele Flammini , Jan van Leeuwen , Alberto Marchetti-Spaccamela, The Complexity of Interval Routing on Random Graphs, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.37-49, August 28-September 01, 1995

14

P. FRAIGNIAUD AND C. GAVOILLE, A theoretical model for routing complexity, in 5th International Colloquium on Structural Information & Communication Complexity (SIROCCO), L. Gargano and D. Peleg, eds., Carleton Scientific, July 1998, pp. 98-113.

15

Pierre Fraigniaud , Cyril Gavoille , Bernard Mans, Interval routing schemes allow broadcasting with linear message-complexity (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.11-20, July 16-19, 2000, Portland, Oregon, United States  [doi>10.1145/343477.343503]

16

G. N. FREDERICKSON, Searching among intervals and compact routing tables, Algorithmica, 15 (1996), pp. 448-466.

17

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

18

Greg N. Frederickson , Ravi Janardan, Efficient message routing in planar networks, SIAM Journal on Computing, v.18 n.4, p.843-857, Aug. 1989  [doi>10.1137/0218058]

19

Greg N. Frederickson , Ravi Janardan, Space-efficient message routing in c-decomposable networks, SIAM Journal on Computing, v.19 n.1, p.164-181, Feb. 1990  [doi>10.1137/0219011]

20

R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983  [doi>10.1145/357195.357200]

21

Cyril Gavoille, A survey on interval routing, Theoretical Computer Science, v.245 n.2, p.217-253, Aug. 28, 2000  [doi>10.1016/S0304-3975(99)00283-2]

22

C. GAVOILLE AND M. GENGLER, Space-efficiency of routing schemes of stretch factor three, in 4th International Colloquium on Structural Information & Communication Complexity (SIROCCO), D. Krizanc and P. Widmayer, eds., Carleton Scientific, July 1997, pp. 162-175.

23

Cyril Gavoille , Nicolas Hanusse, Compact Routing Tables for Graphs of Bounded Genus, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.351-360, July 11-15, 1999

24

Cyril Gavoille , David Peleg, The Compactness of Interval Routing for Almost All Graphs, Proceedings of the 12th International Symposium on Distributed Computing, p.161-174, September 24-26, 1998

25

Cyril Gavoille , Stéphane Pérennès, Memory requirement for routing in distributed networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.125-133, May 23-26, 1996, Philadelphia, Pennsylvania, United States  [doi>10.1145/248052.248075]

26

Yehuda Hassin , David Peleg, Sparse communication networks and efficient routing in the plane (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.41-50, July 16-19, 2000, Portland, Oregon, United States  [doi>10.1145/343477.343514]

27

L. KLEINROCK AND F. KAMOUN, Hierarchical routing for large networks; performance evaluation and optimization, Computer Networks, 1 (1977), pp. 155-174.

28

Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Log-Space Polynomial End-to-End Communication, SIAM Journal on Computing, v.27 n.6, p.1531-1549, Dec. 1998  [doi>10.1137/S0097539795296760]

29

Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997

30

J. I. Munro , V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.118, October 19-22, 1997

31

Lata Narayanan , N. Nishimura, Interval routing on k-trees, Journal of Algorithms, v.26 n.2, p.325-369, feb. 1998  [doi>10.1006/jagm.1997.0880]

32

David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62217]

33

David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989  [doi>10.1145/65950.65953]

34

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

35

J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987  [doi>10.1093/comjnl/30.4.298]

Anupam Gupta , Amit Kumar , Mikkel Thorup, Tree based MPLS routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA

Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.43-52, July 13-16, 2003, Boston, Massachusetts

Zhizhang Shen, An optimal broadcasting schema for multidimensional mesh structures, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida

Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003

Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada

Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain

Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada

Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA

Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002

M. E. Gómez , P. López , J. Duato, FIR: an efficient routing strategy for tori and meshes, Journal of Parallel and Distributed Computing, v.66 n.7, p.907-921, July 2006

H. Arafat Ali , A. I. El-Desouky , M. F. Ared, An IP packet forwarding technique based on a new structure of lookup table, International Journal of Computers and Applications, v.28 n.2, p.112-121, April 2006

Cyril Gavoille , Martin Nehéz, Interval routing in reliability networks, Theoretical Computer Science, v.333 n.3, p.415-432, 3 March 2005

Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: upper bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA

Dmitri Krioukov , kc claffy , Marina Fomenkov , Fan Chung , Alessandro Vespignani , Walter Willinger, The workshop on internet topology (wit) report, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007

Feodor F. Dragan , Irina Lomonosov, On compact and efficient routing in certain graph classes, Discrete Applied Mathematics, v.155 n.11, p.1458-1470, June, 2007

Goran Konjevod , Andrea Werneck Richa , Donglin Xia , Hai Yu, Compact routing with slack in low doubling dimension, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA

Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal scale-free compact routing schemes in networks of low doubling dimension, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.939-948, January 07-09, 2007, New Orleans, Louisiana

Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-12, June 2008

Dominique Tschopp , Suhas Diggavi , Matthias Grossglauser, Hierarchical routing over dynamic wireless networks, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008

Costas Busch , Ryan LaFortune , Srikanta Tirthapura, Improved sparse covers for graphs excluding a fixed minor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA

Zhizhang Shen, Minimal broadcasting schemas for the mesh structures, International Journal of High Performance Computing and Networking, v.2 n.2-4, p.210-221, February 2004

Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Journal of Computer and System Sciences, v.74 n.5, p.775-795, August, 2008

Cyril Gavoille: colleagues