Compact Routing Papers
by Cyril Gavoille

2012

• Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In 44^th Annual ACM Symposium on Theory of Computing (STOC). ACM Press, May 2012.

2011

• Cyril Gavoille. A quick overview on name-independent compact routing schemes. In Euler Project Meeting, November 2011.

• Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In 25^th International Symposium on Distributed Computing (DISC), volume 6950 of Lecture Notes in Computer Science (ARCoSS), pages 404-415. Springer, September 2011. Slides available here.

• Cyril Gavoille and Christian Sommer. Sparse spanners vs. compact routing. In 23^rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 225-234. ACM Press, June 2011. Slides available here.

• Cyril Gavoille. Spanner, distance oracle, and compact routing for unweighted graphs. In ANR Aladdin Meeting, May 2011.

• Youssou Dieng and Cyril Gavoille. Routage compact optimal dans les (k,r)-constellations. Technique et Science Informatiques, 30(n^o 5/2011):485-513, May 2011. See [DG09] for the conference version.

• Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas, and Frédéric Majorczyk. Simulations de routage du schéma AGMaNT. Rapport de contrat (final) DCR - Alcaltel-Lucent Bell, LaBRI, Université Bordeaux, February 2011.

2010

• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-diameter decompositions of minor free graphs. Theory of Computing Systems, 47(4):837-855, November 2010. See [AGMW07] for the conference version.

• Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg. Forbidden-set distance labels for graphs of bounded doubling dimension. In 29^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 192-200. ACM Press, July 2010. Slides available here.

2009

• Cyril Gavoille. Spanner et routage compact : similarités et différences. In 11^èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume inria-00383276. HAL, June 2009. Slides available here.

• Cyril Gavoille. Routing in distributed systems (3 invited lectures). In 1^st Workshop on New Challenges in Distributed Systems, April 2009. [Lecture 1|Lecture 2|Lecture 3].

• Youssou Dieng and Cyril Gavoille. Routage dans les réseaux (k,r)-cellulaires. In 10^èmes Journées Doctorales en Informatique et Réseaux (JDIR), pages 7-12, February 2009. See [DG11] for the journal version.

2008

• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. ACM Transactions on Algorithms, 3(4):Article 37, June 2008. See [AGMNT04] for the conference version.

2007

• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-diameter decompositions of minor free graphs. In 19^th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 16-24. ACM Press, June 2007. See [AGMW10] for the journal version.

• Youssou Dieng and Cyril Gavoille. Routage dans les graphes cellulaires. In 9^èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 91-94, May 2007.

• Cyril Gavoille. An overview on compact routing. In Workshop on Peer-to-Peer, Routing in Complex Graphs, and Network Coding, March 2007. See web pages here.

• Tamar Eilam, Cyril Gavoille, and David Peleg. Average stretch analysis of compact routing schemes. Discrete Applied Mathematics, 155:598-610, January 2007. Appears also as RR-1195-98 (1998).

2006

• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strongly-bounded sparse decompositions of minor free graphs. Technical Report MSR-TR-2006-192, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2006. See [AGMW10] for the journal version.

• Cyril Gavoille. An overview on compact routing. In 2^nd Research Workshop on Flexible Network Design, October 2006. See web pages here.

• Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26^th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, July 2006. See [AGGM05] for the TR version. Slides available here: .ppt and .pdf.

• Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 188-197. ACM Press, July 2006. Slides available here.

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: Upper bounds. In 18^th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 207-216. ACM Press, July 2006. Slides available here.

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: Lower bounds. In 18^th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 217-224. ACM Press, July 2006. Slides available here.

• Ittai Abraham and Cyril Gavoille. Object location using path separators. Research Report RR-1394-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2006. Original URL. Extended abstract published in PODC '06.

2005

• Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. Technical Report MSR-TR-2005-175, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2005. See [AGGM06] for the conference version.

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs for compact routing schemes. Research Report RR-1374-05, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 2005. Original URL.

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19^th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442-456. Springer, September 2005. Slides available here.

• Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. Theoretical Computer Science, 333(3):415-432, 2005. An extended abstract appears in SIROCCO '03 (invited for the Sirocco special issue).

2004

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In 18^th International Symposium on Distributed Computing (DISC), volume 3274 of Lecture Notes in Computer Science, pages 305-319. Springer, October 2004. The full version appears in RR-1330-04 (2004).

• Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. Research Report RR-1330-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, July 2004. Original URL. Extended abstract published in DISC '04.

• Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. In 16^th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 20-24. ACM Press, July 2004. See [AGMNT08] for the journal version. Slides available here.

2003

• Cyril Gavoille and Martin Nehéz. On interval routing in random meshes. In J. Fila, editor, 2^nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 147-150, September 2003. A revised appears in Theoretical Computer Science.

• Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. In 9^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 149-164. Carleton University Press, June 2003. Slides available here. Appears also as RR-1294-03 (2003), and a revised appears in Theoretical Computer Science.

• Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Journal of Discrete Algorithms, 1(2):237-254, April 2003. Extended abstract published in SIROCCO '00. Appears also as RR-1233-00 (2000).

• Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. Research Report RR-1294-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2003. Original URL. An extended abstract appears in SIROCCO '03, and a revised appears in Theoretical Computer Science.

• Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46(2):97-114, 2003. Extended abstract published in PODC '98. Appears also as RR-1195-98 (1998).

2002

• Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. In 16^th International Symposium on Distributed Computing (DISC), volume 2508 of Lecture Notes in Computer Science, pages 252-264. Springer, October 2002. An updated version is available here. Appears also as RR-1274-02 (2002).

• Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. Research Report RR-1274-02, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2002. Original URL. Extended abstract published in DISC '02.

• Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In 19^th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2285 of Lecture Notes in Computer Science, pages 65-75. Springer, March 2002. Slides available here.

2001

• Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. Research Report RR-1262-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2001. Original URL. Extended abstract published in STACS '02.

• Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. Distributed Computing, 14(4):217-229, July 2001. Extended abstract published in PODC '00. Appears also as LRI-1241 (2000).

• Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, 28^th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757-772. Springer, July 2001. Slides available here.

• Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating sets in planar graphs with applications. In 27^th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2204 of Lecture Notes in Computer Science, pages 201-216. Springer, June 2001. A revised version is available here.

• Cyril Gavoille. Compact and distributed data structures (invited lecture). In IWIN-SIROCCO '01 joint conference, June 2001. Slides available here.

• Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating sets in planar graphs with applications. Research Report RR-1258-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2001. Original URL. Extended abstract published in WG '01, and a revised version is available here.

• Pierre Fraigniaud and Cyril Gavoille. Comment router dans un arbre ?. In 3^èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 85-88. INRIA, May 2001. Slides available here.

• Yon Dourisboure and Cyril Gavoille. Interval routing for generalized Hypercube-like graphs. In 3^èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 61-68. INRIA, May 2001.

• Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column, 32(1):36-52, March 2001.

• Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. SIAM Journal on Computing, 31(3):706-721, 2001. Extended abstract published in DISC '98. Appears also as RR-1202-98 (1998).

• Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61(5):679-687, 2001. Updated version of RR-1181-97 (1997).

• Pierre Fraigniaud and Cyril Gavoille. Routing in trees. Research Report RR-1252-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, January 2001. Original URL. Extended abstract published in ICALP '01.

2000

• Cyril Gavoille. Structures de données compactes et distribuées, December 2000. Thèse d'habilitation à diriger les recherches, Université de Bordeaux, Slides available here.

• Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. In 19^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, July 2000. The full version appears in JDC. Appears also as LRI-1241 (2000).

• Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. In Michele Flammini, Enrico Nardelli, Guido Proietti, and Paul Spirakis, editors, 7^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 127-140. Carleton Scientific, June 2000. Extended abstract of RR-1233-00 (2000). An updated version is available in Journal of Discrete Algorithms. Slides available here.

• Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Research Report RR-1233-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2000. Original URL. Extended abstract published in SIROCCO '00, and an updated version is available in Journal of Discrete Algorithms.

• Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245(2):217-253, 2000. Updated version of RR-1182-97 (1997).A HTML version available here.

• Cyril Gavoille. On the dilation of interval routing. The Computer Journal, 43(1):243-249, 2000. Updated version of RR-1145-96 (1996).

• Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. Research Report LRI-1241, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. Extended abstract published in PODC '00, and the full version appears in JDC.

1999

• Cyril Gavoille and David Peleg. The compactness of interval routing. SIAM Journal on Discrete Mathematics, 12(4):459-473, October 1999. Updated version of RR-1176-97 (1997).

• Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Ji\vrí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, 26^th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, pages 351-360. Springer, July 1999. Extended abstract of RR-1213-99 (1999), and a revised version is available here.

• Cyril Gavoille and Nicolas Hanusse. Routage compact dans les réseaux de genre borné. In 1^ère Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1-5. INRIA, May 1999. Apparaît aussi dans RR-1213-99 (1999).

• Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. Research Report RR-1213-99, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 1999. Original URL. Extended abstract published in ICALP '99, and a revised version is available here.

1998

• Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. In Shay Kutten, editor, 12^th International Symposium on Distributed Computing (DISC), volume 1499 of Lecture Notes in Computer Science, pages 161-174. Springer, September 1998. An updated version appears in SIAM J. on Computing. Appears also as RR-1202-98 (1998). Slides available here.

• Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. In 17^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, August 1998. An updated version appears in Journal of Algorithms. Appears also as RR-1195-98 (1998). Slides available here.

• Pierre Fraigniaud and Cyril Gavoille. A theoretical model for routing complexity. In Luisa Gargano and David Peleg, editors, 5^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 98-113. Carleton Scientific, July 1998.

• Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. Research Report RR-1202-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, April 1998. Original URL. Extended abstract published in DISC '98, and a revised version appears in SIAM J. on Computing.

• Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Journal of Algorithms, 27(1):1-25, 1998. Updated version of RR95-02 (1995).

• Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Algorithmica, 21:155-182, 1998. Updated version of RR94-04 (1994).

• Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Research Report RR-1195-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, January 1998. Original URL. A part appears in Journal of Algorithms (and an extended abstract has been published in PODC '98), and another part appears here.

1997

• Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Research Report RR-1181-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. Original URL. Extended abstract published in SIROCCO '97. Appears also in JPDC.

• Cyril Gavoille. A survey on interval routing scheme. Research Report RR-1182-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. Original URL. An updated version appears in TCS, and a HTML version available here.

• Cyril Gavoille and David Peleg. The compactness of interval routing. Research Report RR-1176-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 1997. Original URL. An updated version appears in SIAM Journal on Discrete Mathematics.

• Cyril Gavoille. On the dilation of interval routing. In Igor Prívara and Peter Ru\vzi\vcka, editors, 22^nd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 1300 of Lecture Notes in Computer Science, pages 259-268. Springer, August 1997. Appears also as RR-1145-96 (1996).

• Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. In Danny Krizanc and Peter Widmayer, editors, 4^th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 162-175. Carleton Scientific, July 1997. Appears also as RR-1181-97 (1997).

• Cyril Gavoille. Compact routing: Lower bounds techniques (invited lecture). In International Research School on "Sense of Direction and Compact Routing", June 1997.

• Pierre Fraigniaud and Cyril Gavoille. Universal routing schemes. Distributed Computing, 10:65-78, 1997. Updated version of RR95-05 (1995).

1996

• Cyril Gavoille. On dilation of interval routing. Research Report RR-1145-96, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 1996. Original URL. An updated version appears in The Computer Journal and in MFCS '97.

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

• Cyril Gavoille and Stéphane Pérennès. Lower bounds for interval routing on 3-regular networks. In Nicola Santoro and Paul Spirakis, editors, 3^rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 88-103. Carleton University Press, June 1996.

• Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. In 8^th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 183-188. ACM Press, June 1996. Appears also as RR96-01 (1996). Appears also in Journal of Distributed Computing (1997).

• Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In 15^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125-133. ACM Press, May 1996. BEST STUDENT PAPER AWARD. Appears also as RR95-46 (1995) and I3S 95-37 (1995).

• Cyril Gavoille and Stéphane Pérennès. Lower bounds for shortest path interval routing. Research Report 96-08, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, April 1996. Original URL.

• Cyril Gavoille. Complexité mémoire du routage dans les réseaux distribués. PhD thesis, École Normale Supérieure de Lyon, 46, allée d'Italie, January 1996. The cover page is available here.

• Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. Research Report 96-01, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1996. Original URL. Extended abstract published in SPAA '96.

1995

• Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. Research Report 95-46, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, December 1995. Original URL. Extended abstract published in PODC '96.

• Cyril Gavoille and Stéphane Pérennès. Routing memory requirement for distributed networks. Research Report 95-37, I3S, Université de Nice-Sophia Antipolis, 06903 Sophia Antipolis, France, August 1995. Extended abstract published in PODC '96.

• Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. In 14^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 223-230. ACM Press, August 1995. An updated version is available in the Journal of Distributed Computing.

• Cyril Gavoille and Eric Guévremont. On the compactness of bounded degree graphs for shortest path interval routing. In Lefteris M. Kirousis and Evangelos Kranakis, editors, 2^nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 113-121. Carleton University Press, June 1995.

• Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. Research Report 95-05, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, March 1995. Original URL. An updated version is available in the Journal of Distributed Computing.

• Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Research Report 95-02, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1995. Original URL. An updated version appears in Journal of Algorithms.

1994

• Pierre Fraigniaud and Cyril Gavoille. Optimal interval routing. In Bruno Buchberger and Jens Volkert, editors, Parallel Processing: CONPAR '94 - VAPP VI, volume 854 of Lecture Notes in Computer Science, pages 785-796. Springer-Verlag, September 1994.

• Pierre Fraigniaud and Cyril Gavoille. A characterization of networks supporting linear interval routing. In 13^th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 216-224. ACM Press, August 1994.

• Cyril Gavoille. Routages efficaces et compacts. In Luc Bougé, Michel Cosnard, and Pierre Fraigniaud, editors, 6^èmes Rencontres Francophones du Parallélisme (RenPar), page 298, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1994.

• Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Research Report 94-04, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1994. Original URL. An updated version appears in Algorithmica.

1993

• Cyril Gavoille. Routage par intervalles. Stage de DEA, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1993.