21 décembre 2024, 12:56:55

#papers: 103

Compact Routing Papers
by Cyril Gavoille

[ 2017 | 2016 | 2015 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997 | 1996 | 1995 | 1994 | 1993]

2017

Cyril Gavoille. Compact and distributed data structures. In 44e École de Printemps en Informatique Théorique (EPIT) -- Distributed Computing, May 2017. See epit2017.labri.fr.

2016

Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg. Forbidden-set distance labels for graphs of bounded doubling dimension. ACM Transactions on Algorithms, 12(2):Article No. 22, pp. 1–17, February 2016. See [ACGP10] for the conference version.

2015

Cyril Gavoille. An overview on compact routing (in discrete domains). In CMO-BIRS Workshop on Searching and Routing in Discrete and Continuous Domains, October 2015. Video available here or here.
Cyril Gavoille, Christian Glacet, Nicolas Hanusse, and David Ilcinkas. Brief announcement: Routing the Internet with very few entries. In 34th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 33–35. ACM Press, July 2015. Slides available here.
Cyril Gavoille, Christian Glacet, Nicolas Hanusse, and David Ilcinkas. Router dans internet avec quinze entrées. In 17es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume hal-01149335. HAL, May 2015. See here for the HAL version. Slides available here.

2013

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, and David Ilcinkas. On the communication complexity of distributed name-independent routing schemes. In 27th International Symposium on Distributed Computing (DISC), volume 8205 of Lecture Notes in Computer Science, pages 418–432. Springer, October 2013. Slides available here.
Cyril Gavoille, Christian Glacet, Nicolas Hanusse, and David Ilcinkas. Algorithme distribué de routage compact en temps optimal. In 15es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume hal-00818445, pages 117–120. HAL, May 2013. See here for the HAL version.

2012

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

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 25th 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 23rd 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(5):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 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 192–200. ACM Press, July 2010. See [ACGP16] for the journal version. Slides available here.

2009

Cyril Gavoille. Spanner et routage compact : similarités et différences. In 11es 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 1st 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 10es 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 No. 37, pp. 1–12, 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 19th 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 9es 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(5):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 2nd 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 26th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, July 2006. Slides available here: .ppt and .pdf.
Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25th 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 18th 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 18th 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 19th 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, March 2005. See [GN03] for the conference version (invited for the Sirocco special issue).

2004

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In 18th 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 16th 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.
Cyril Gavoille. Routage avec indépendance des noms. In ACI PairApair Meeting, January 2004.

2003

Cyril Gavoille and Martin Nehéz. On interval routing in random meshes. In J. Fila, editor, 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 147–150, September 2003. See [GN05] for the journal version.
Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. In 9th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 149–164. Carleton University Press, June 2003. Slides available here. See [GN03a] for the TR version. See [GN05] for the journal version.
Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Journal of Discrete Algorithms, 1(2):237–254, April 2003. See [GZ00a] for the conference version. See [GZ00] for the TR version.
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. See [GN03] for the conference version. See [GN05] for the journal version.
Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46(2):97–114, February 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 16th 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 19th 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, 28th 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 27th 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. See [GPRS01] for the conference version. See ["http://dept-info.labri.fr/~gavoille/article/GPRS01_up"] for an updated version.
Pierre Fraigniaud and Cyril Gavoille. Comment router dans un arbre ?. In 3es 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 3es 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. See [GP98a] for the conference version. See [GP98] for the TR version.
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. See [GG97a] for the TR version.
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.
Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245(2):217–253, August 2000. See [Gav97a] for the TR version. A HTML version available here.
Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. In 19th 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 G. Spirakis, editors, 7th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 127–140. Carleton Scientific, June 2000. See [GZ00] for the TR version. See [GZ03] for the journal version. 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. See [GZ00a] for the conference version. See [GZ03] for the journal version.
Cyril Gavoille. On the dilation of interval routing. The Computer Journal, 43(1):243–249, 2000. See [Gav96c] for the TR version.
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. See [GP97] for the TR version.
Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Jiří Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, 26th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, pages 351–360. Springer, July 1999. See [GH99a] for the TR version. See ["http://dept-info.labri.fr/~gavoille/article/GH99_up"] for an updated version.
Cyril Gavoille and Nicolas Hanusse. Routage compact dans les réseaux de genre borné. In 1ères Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1–5. INRIA, May 1999. See [GH99a] for the TR version.
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. See [GH99] for the conference version. See ["http://dept-info.labri.fr/~gavoille/article/GH99_up"] for an updated version.

1998

Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. In Shay Kutten, editor, 12th International Symposium on Distributed Computing (DISC), volume 1499 of Lecture Notes in Computer Science, pages 161–174. Springer, September 1998. See [GP01] for the journal version. See [GP98] for the TR version. Slides available here.
Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. In 17th 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, 5th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 98–113. Carleton Scientific, July 1998.
Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Algorithmica, 21(2):155–182, June 1998. Updated version of RR94-04 (1994).
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. See [GP98a] for the conference version. See [GP01] for the journal version.
Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Journal of Algorithms, 27(1):1–25, April 1998. See [GG95] for the TR version.
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. See [GG97] for the conference version. See [GG01] for the journal version.
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. See [Gav00] for the journal version, 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. See [GP99] for an updated version.
Cyril Gavoille. On the dilation of interval routing. In Igor Prívara and Peter Ružička, editors, 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 1300 of Lecture Notes in Computer Science, pages 259–268. Springer, August 1997. See [Gav96c] for the TR version.
Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. In Danny Krizanc and Peter Widmayer, editors, 4th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 162–175. Carleton Scientific, July 1997. See [GG97a] for the TR version.
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. See [Gav00a] for the journal version. See [Gav97] for the conference version.
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 G. Spirakis, editors, 3rd 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 8th 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 Distributed Computing (1997).
Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125–133. ACM Press, May 1996. BEST STUDENT PAPER AWARD. See [GP95a] for the TR version and here.
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. See [GP96b] for the conference version.
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. See [GP96b] for the conference version.
Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. In 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 223–230. ACM Press, August 1995. An updated version is available in 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, 2nd 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 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. See [GG98] for the journal version.

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 13th 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, 6es 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.

Compact Routing Papersby Cyril Gavoille