Cyril GAVOILLE
List of Publications (exhaustive)

(bibtex format)
Compact routing papers
Co-authors
[My Biblio]
[My home page]
Copyrights for some of the papers below have been transfered, or will be transfered to various publishers of journals, conferences proceedings, etc. For such papers I am required to post the following notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. Publisher's copyright policy are available at © SIAM, © ACM, © IEEE, © Springer, © Elsevier, © King's College.

2024

  1. Edgar Baucher, Francois Dross, Cyril Gavoille, and Amaury Jacques. Super-graphe de deux arbres: entre P et NPC. In 26es Journées Graphes et Algorithmes, November 2024.

  2. Bonamy Marthe, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek. Algorithmes distribués et dimension asymptotique. In 26es Journées Graphes et Algorithmes, November 2024.

  3. Cyril Gavoille and Amaury Jacques. Graphe universel pour les graphes sans mineur. In 26es Journées Graphes et Algorithmes, November 2024.

  4. Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse. Freeze-tag in L1 has wake-up time five with linear complexity. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing (DISC), volume 319 of LIPIcs, pages 9:1–9:16, October 2024. See [BCGH24a] for the TR version. Slides available here.

  5. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Saeed Odak. Euclidean freeze-tag problem on plane. In 36th Canadian Conference on Computational Geometry (CCCG), pages 199–205, July 2024.

  6. Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse. Freeze-tag in L1 has wake-up time five. Technical Report 2402.03258v1 [cs.DS], arXiv, February 2024. See [BCGH24] for the conference version.

  7. Cyril Gavoille. Techniques algorithmiques et programmation, 2024. Notes de cours.

  8. Cyril Gavoille. Analyse d'algorithme -- Cours d'introduction à la complexité paramétrique et aux algorithmes d'approximation, 2024. Notes de cours.

  9. Cyril Gavoille. Algorithmique distribuée, 2024. Notes de cours.


2023

  1. Edgar Baucher, Francois Dross, and Cyril Gavoille. Graphes universels isométriques. In 25es Journées Graphes et Algorithmes, page 25, November 2023. Slides available here.

  2. Cyril Gavoille and Claire Hilaire. Graphes mineur-universels pour les graphes plongés sur des surfaces. In 25es Journées Graphes et Algorithmes, page 23, November 2023. Slides available here.

  3. Claire Hilaire and Cyril Gavoille. Minor-universal graph for graphs on surfaces (poster), August 2023. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB).

  4. Cyril Gavoille and Claire Hilaire. Minor-universal graph for graphs on surfaces. Technical Report hal-04090935, HAL, May 2023. Appears also here as arXiv 2305.06673v1 [cs.DM].

  5. Cyril Gavoille. On the freeze-tag problem. In GT Graphes et Optimisation, April 2023. Video available here.


2022

  1. Cyril Gavoille. Smaller universal graphs for caterpillars and graphs of bounded path-width (part I & II). In GT Graphes et Optimisation, December 2022.

  2. Cyril Gavoille and Amaury Jacques. Graphes universels pour de petites familles de graphes. In 24es Journées Graphes et Algorithmes, November 2022.

  3. Cyril Gavoille. A succinct story of compact stuff. In FRAIGNIAUD Workshop, November 2022.

  4. Cyril Gavoille. On the freeze-tag problem. In ANR TEMPOGRAL Meeting, November 2022.

  5. Cyril Gavoille. Smaller universal graphs for caterpillars and graphs of bounded path-width. In 2nd Workshop on Complexity and Algorithms (CoA), September 2022.

  6. Cyril Gavoille and Arnaud Labourel. Smaller universal graphs for caterpillars and graphs of bounded path-width. In 11th International Colloquium on Graph Theory (ICGT), page Paper No. 54, July 2022. Slides available here.

  7. Cyril Gavoille. An optimal algorithm for the Freeze-Tag Problem in 2D. Software, LaBRI, Université Bordeaux, March 2022.

  8. Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs. SIAM Journal on Discrete Mathematics, 36(3):2082–2099, 2022. See [BGP20] for the conference version.


2021

  1. Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). Journal of the ACM, 68(6):Article No. 42, pp. 1–33, December 2021. See [DEGJx20] for the conference version.

  2. Cyril Gavoille and Claire Hilaire. Grilles majeures de graphes dessinés. In 23es Journées Graphes et Algorithmes, November 2021.

  3. Cyril Gavoille. Universal graph and implicit representation of planar graphs. In Séminaire du Laboratoire d'Informatique Gaspard-Monge (LIGM), November 2021.

  4. Keren Censor-Hillel, Pierre Fraigniaud, Cyril Gavoille, Seth Gilbert, Andrzej Pelc, and David Peleg. 2021 Edsger W. Dijkstra prize in distributed computing. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, 40th Annual ACM Symposium on Principles of Distributed Computing (PODC), page 1. ACM Press, July 2021.

  5. Louis Esperet, Cyril Gavoille, and Carla Groenland. Isometric universal graphs. Technical Report 2103.08570v1 [math.CO], arXiv, March 2021. See [EGG21a] for the journal version.

  6. Cyril Gavoille. Universal graphs. In Journées de Combinatoire de Bordeaux, February 2021. Video available here.

  7. Louis Esperet, Cyril Gavoille, and Carla Groenland. Isometric universal graphs. SIAM Journal on Discrete Mathematics, 5(2):1224–1237, 2021. See [EGG21] for the TR version.


2020

  1. Cyril Gavoille and Claire Hilaire. Dessin et mineur de graphe. In 22es Journées Graphes et Algorithmes, page 47, November 2020. Slides available here("http://dept-info.labri.fr/~gavoille/article/GH20s".

  2. Cyril Gavoille. Adjacency labelling for planar graphs (and beyond). In GT Algorithmique Distribuée, November 2020.

  3. Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). In 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 577–588. IEEE Computer Society Press, November 2020. Video available here or here. See [DEGJx21] for the journal version. See [DEGJx20a] for the TR version.

  4. Cyril Gavoille. Notes on the paper ``short labels by traversal and jumping'', October 2020. Personnal notes.

  5. Cyril Gavoille. Consequences for adjacency labelling schemes. In Journées Combinatoire Rhône-Alples, Auvergne, Littoral Méditerranéen et Athlantique (JCRAALMA), May 2020. Video available here.

  6. Youssou Dieng and Cyril Gavoille. On the treewidth of planar minor free graphs. In Jessica P.R. Thorn, Assane Gueye, and Adam P. Hejnowicz, editors, 4th EAI International Conference on Innovations and Interdisciplinary Solutions for Underserved Areas (InterSol), volume 321 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 238–250. Springer, Cham, March 2020. BEST PAPER AWARD. Slides available here.

  7. Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). Technical Report 2003.04280v1 [cs.DS], arXiv, March 2020. See [DEGJx20] for the conference version. See [DEGJx21] for the journal version.

  8. Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs. In Shuchi Chawla, editor, 31st Symposium on Discrete Algorithms (SODA), pages 446–462. ACM-SIAM, January 2020. Slides available here. See [BGP19] for the TR version. See [BGP22] for the journal version.


2019

  1. Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Smaller induced-universal graph for planar graphs. In Bordeaux Graph Workshop (BGW), pages 65–68, October 2019. Slides available here. See [BGP19] for the TR version. See [BGP22] for the journal version.

  2. Cyril Gavoille, Ghazal Kachigar, and Gilles Zémor. Localisation-resistant random words with small alphabets. In R. Mercas and D. Reidenbach, editors, 12th International Conference on Combinatorics on Words (WORDS), volume 11682 of Lecture Notes in Computer Science, pages 193–206. Springer, September 2019. Slides available here.

  3. Cyril Gavoille. Shorter implicit representation for planar graphs. In GT Graphes et Optimisation, September 2019.

  4. Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs. Technical Report hal-02265219, HAL, August 2019. See [BGP22] for the journal version. Appears also here as arXiv:1908.0334v1 [cs.DS].

  5. Cyril Gavoille. Shorter implicit representation for planar graphs. In Sergio Cabello and Bojan Mohar, editors, 9th Slovenian International Conference on Graph Theory (SICGT), page 63. Institute of Mathematics, Physics and Mechanics (IMFM), June 2019. Slides available here. See web pages here.

  6. Cyril Gavoille. Distributed computing with quantum resources and beyond. In Complexity, Algorithms, Automata and Logic Meet (CAALM), January 2019. See web pages here.

  7. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120–1145, January 2019.


2018

  1. Christian Barillot, Inbar Fijalkow, Isabelle Queinnec, Fabrice Théoleyre, Hélène Touzet, Michel Beaudouin-Lafon, Marie-Paule Cani, Francois Chaumette, Gérald Conreur, Véronique Cortier, Cyril Gavoille, Guy Gogniat, Julien Gossa, Andreas Herzig, Jean Krivine, Philippe Lamarre, Francoise Lamnabhi, Anne-Catherine Letournel, Lionel Seinturier, Isabelle Tellier, Serge Torres, Charlotte Truchet, Alexandros Tsoukias, and Michel Verleysen. Rapport de prospective du conseil scientifique de l'institut des sciences de l'information et leurs interactions (INS2I). Technical Report hal-01956087, HAL, December 2018.

  2. Cyril Gavoille. Introduction à la complexité de communication. In GT Algorithmique Distribuée, November 2018.


2017

  1. 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.

  2. Cyril Gavoille. Beyond classical local models in distributed computing. In 44e École de Printemps en Informatique Théorique (EPIT) -- Distributed Computing, May 2017. See epit2017.labri.fr.

  3. Ahmad Biniaz, Prosenjit Bose, Jean-Lou de Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards plane spanners of degree 3. Technical Report 1606.08824v2 [cs.CG], arXiv, February 2017. See [BBdCx17] for the journal version.

  4. Ahmad Biniaz, Prosenjit Bose, Jean-Lou de Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards plane spanners of degree 3. Journal of Computational Geometry, 8(1):11–31, 2017. See [BBdCx17a] for the TR version.


2016

  1. Ahmad Biniaz, Prosenjit Bose, Jean-Lou de Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards plane spanners of degree 3. In Seok-Hee Hong, editor, 27th Annual International Symposium on Algorithms and Computation (ISAAC), volume 64 of LIPIcs, pages 19:1–19:14, December 2016. !SVJ(BBdCx17). See [BBdCx17a] for the TR version.

  2. Cyril Gavoille and David Ilcinkas. Proceedings of the 30th international symposium on distributed computing, disc 2016, paris, france, september 27-29, 2016, volume 9888 of Lecture Notes in Computer Science (ARCoSS). Springer, September 2016. PDF on Springer or here.

  3. 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.

  4. Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, and Holger Petersen. Simpler, faster and shorter labels for distances in graphs. In 27th Symposium on Discrete Algorithms (SODA), pages 338–350. ACM-SIAM, January 2016. See [AGHP15] for the TR version.


2015

  1. 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.

  2. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. In Christian Scheideler, editor, 22nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 9439 of Lecture Notes in Computer Science, pages 209–223. Springer, July 2015.

  3. 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.

  4. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. Technical Report 1505.05697 [cs.DC], arXiv, May 2015.

  5. 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.

  6. Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, and Holger Petersen. Simpler, faster and shorter labels for distances in graphs. Technical Report 1504.04498v1 [cs.DS], arXiv, April 2015. Slides available here: .ppt and .pdf.

  7. Cyril Gavoille. Computing distances in a graph in constant time and with 0.793n-bit labels. In ANR Displexity Meeting, March 2015.

  8. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Tight stretch factors for L1- and L\infty-Delaunay triangulations. Computational Geometry: Theory and Applications, 48:237–250, 2015. See [BGHP12] for the conference version.


2014

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. In 46th Annual ACM Symposium on Theory of Computing (STOC), pages 79–88. ACM Press, May 2014.

  2. Cyril Gavoille. Data structures for emergency planning. In 8th Foundations of Information and Knowledge Systems (FoIKS), volume 8367 of Lecture Notes in Computer Science (ARCoSS). Springer, March 2014. Slides available here.


2013

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. Technical Report 1311.3048v1 [cs.DS], arXiv, November 2013.

  2. 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.

  3. Cyril Gavoille. Labeling schemes with forbidden-sets. In 20th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 8179 of Lecture Notes in Computer Science. Springer, July 2013. Slides available here.

  4. 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

  1. Cyril Gavoille and Pierre Halftermeyer. Connectivity labeling scheme for graphs on surface. In Bordeaux Graph Workshop (BGW), pages 69–70, November 2012. Slides available here.

  2. Cyril Gavoille. Progress and challenges for labeling schemes. In First International Workshop on Advances in Distributed Graph Algorithms (ADGA), October 2012.

  3. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. The stretch factor of L1- and L\infty-Delaunay triangulations. In Leah Epstein and Paolo Ferragina, editors, 20th Annual European Symposium on Algorithms (ESA), volume 7501 of Lecture Notes in Computer Science, pages 205–216. Springer-Verlag, September 2012. See [BGHP12a] for the TR version.

  4. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. The stretch factor of L1- and L\infty-Delaunay triangulations, May 2012. Poster at STOC '12, See [BGHP12] for the conference version.

  5. Cyril Gavoille and Pierre Halftermeyer. Connexité dans l'urgence. In 14es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume hal-00690561, pages 75–78. HAL, May 2012. Slides available here.

  6. 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.

  7. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. The stretch factor of L1- and L\infty-Delaunay triangulations. Technical Report hal-00673187v2/1202.5127v2 [cs.GC], HAL/arXiv, February 2012.


2011

  1. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Node-disjoint multipath spanners and their relationship with fault-tolerant spanners. In 15th International Conference on Principles of Distributed Systems (OPODIS), volume 7109 of Lecture Notes in Computer Science, pages 143–158. Springer, December 2011. See [GGV11a] for the TR version. Slides available here.

  2. Cyril Gavoille. Dynamic algorithms via forbidden-set labeling. In First International Workshop on Dynamic Systems (DYNAM), December 2011.

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

  4. 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.

  5. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Node-disjoint multipath spanners and their relationship with fault-tolerant spanners. Technical Report hal-00622915, HAL, September 2011. See [GGV11] for the conference version.

  6. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. An information-theoretic upper bound on planar graphs using well-orderly maps. In Matthias Dehmer, Frank Emmert-Streib, and Alexander Mehler, editors, Towards an Information Theory of Complex Networks, chapter 2, pages 17–46. Birkhäuser Boston, July 2011. See [BGH03] for the conference version.

  7. 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.

  8. Pierre Fraigniaud and Cyril Gavoille. Proceedings of the 30th annual acm symposium on principles of distributed computing (podc). ACM Press, June 2011.

  9. 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.

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

  11. Cyril Gavoille. Oracles pour les arbres et les graphes. In 10 ans du séminaire MaMux - Mathématiques, musique et relations avec d'autres disciplines, May 2011.

  12. Émilie Diot, Cyril Gavoille, and Pascal Ochem. Sur la difficulté de séparer un graphe par des plus courts chemins. In 13es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume inria-00588312, pages 65–72. HAL, May 2011.

  13. 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.

  14. Bruno Courcelle, Cyril Gavoille, and Mamadou Moustapha Kanté. Compact labelings for efficient first-order model-checking. Journal of Combinatorial Optimization, 21(1):19–46, January 2011. See [CGK08] for the conference version.


2010

  1. Cyril Gavoille, Boaz Patt-Shamir, and Christian Scheideler. Special issue: Parallelism on Algorithms and Architectures (SPAA). Theory of Computing Systems, 47(4):809–962, November 2010.

  2. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Spanners additifs de taille sous-quadratique pour les graphes orientés. In 12es Journées Graphes et Algorithmes, page 9, November 2010. Slides available here.

  3. 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.

  4. Émilie Diot and Cyril Gavoille. La hiérarchie des graphes k-chemin séparables. In 12es Journées Graphes et Algorithmes, page 7, November 2010. Slides available here.

  5. Émilie Diot and Cyril Gavoille. Path separability of graphs. Technical Report hal-00507833, HAL, September 2010. See [DG10] for the conference version.

  6. Émilie Diot and Cyril Gavoille. Path separability of graphs. In 4th International Frontiers of Algorithmics Workshop (FAW), volume 6213 of Lecture Notes in Computer Science, pages 262–273. Springer, August 2010. See [DG10a] for the TR version.

  7. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Plane spanners of maximum degree six. In 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science (ARCoSS), pages 19–30. Springer, July 2010. Slides available here.

  8. Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis. Proceedings of the 37th international colloquium on automata, languages and programming, icalp 2010, bordeaux, france, july 6-10, 2010, part I & II, volume 6198 & 6199 of Lecture Notes in Computer Science (ARCoSS). Springer, July 2010. Part I on Springer or here & Part II on Springer or here.

  9. 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.

  10. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, David Ilcinkas, and Ljubomir Perković. Comment résumer le plan. In 12es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume inria-00476151. HAL, June 2010. See also [BGHI10] and [BGHP10].

  11. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and David Ilcinkas. Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 6410 of Lecture Notes in Computer Science (ARCoSS), pages 266–278. Springer, June 2010. See [BGHI10a] for the TR version. Slides available here.

  12. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Multipath spanners. In 17th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 6058 of Lecture Notes in Computer Science, pages 211–223. Springer, June 2010. See ["http://dept-info.labri.fr/~gavoille/article/GGV10u"] for an updated version.

  13. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Graphes de recouvrement multichemins. In 12es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume inria-00475970. HAL, June 2010. See ["http://dept-info.labri.fr/~gavoille/article/GGV10u"] for an updated version.

  14. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and David Ilcinkas. Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. Technical Report hal-00454565, HAL, February 2010. See [BGHI10] for the conference version.

  15. Marcin Markiewicz, Adrian Kosowski, Tomasz Tylec, Jarosław Pykacz, and Cyril Gavoille. Static quantum games revisited. Technical Report 1001.2257v3 [quant-ph], arXiv, January 2010. Submitted to Physics Letters A.


2009

  1. Youssou Dieng and Cyril Gavoille. On the tree-width of planar graphs. In European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), volume 34 of Electronic Notes in Discrete Mathem atics, pages 593–596. Elsevier, September 2009. Slides available here.

  2. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local computation of nearly additive spanners. In 23rd International Symposium on Distributed Computing (DISC), volume 5805 of Lecture Notes in Computer Science, pages 176–190. Springer, September 2009.

  3. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? Round-based models for quantum distributed computing. In 23rd International Symposium on Distributed Computing (DISC), volume 5805 of Lecture Notes in Computer Science, pages 243–257. Springer, September 2009. See [GKM09a] for the TR version. Slides available here.

  4. Émilie Diot and Cyril Gavoille. On the path separability of planar graphs. In European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), volume 34 of Electronic Notes in Discrete Mathematics, pages 549–552. Elsevier, September 2009.

  5. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Łukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Networks, 54(1):12–19, August 2009. See [GKKKN07b] for the TR version.

  6. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 309(11):3465–3484, June 2009. See [BG05b] for the conference version.

  7. 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.

  8. Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, and Zvi Lotker. Universal augmentation schemes for network navigability: Overcoming the √n-barrier. Theoretical Computer Science, 410(21-23):1970–1981, May 2009. See [FGKLL07] for the conference version.

  9. 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].

  10. Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and David Andrew Twigg. Optimal labelling for connectivity checking in planar networks with obstacles. Technical Report hal-00367746, HAL, March 2009. See [CGKT08] for the conference version.

  11. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? Round-based models for quantum distributed computing. Technical Report 0903.1133v1 [quant-ph], arXiv, March 2009. See [GKM09] for the conference version.

  12. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: Information sensitivity of graph coloring. Distributed Computing, 21(6):395–403, March 2009. See [FGIP08] for the conference version.

  13. 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

  1. Youssou Dieng and Cyril Gavoille. La structure des graphes sans mineur K2,4. In 10es Journées Graphes et Algorithmes, November 2008.

  2. Bruno Courcelle, Cyril Gavoille, and Mamadou Moustapha Kanté. Compact labelings for efficient first-order model-checking. Technical Report hal-00342668, HAL, November 2008. See [CGK08] for the conference version. See [CGK11] for the journal version. The paper appears also here as arXiv:0811.4713 [cs.DS].

  3. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed sparse spanner construction. In 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 273–282. ACM Press, August 2008. See [DGPV08] for the TR version. Slides available here.

  4. Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and David Andrew Twigg. Connectivity check in 3-connected planar graphs with obstacles. In International Conference on Topological & Geometric Graph Theory (TGGT), volume 31 of Electronic Notes in Discrete Mathematics, pages 151–155, August 2008. See [CGKT09] for an updated version. Slides available here.

  5. Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM Journal on Discrete Mathematics, 22(3):1239–1258, July 2008. See [GP03] for the conference version.

  6. Bruno Courcelle, Cyril Gavoille, and Mamadou Moustapha Kanté. Efficient first-order model-checking using short labels. In 2nd International Frontiers of Algorithmics Workshop (FAW), volume 5059 of Lecture Notes in Computer Science, pages 159–170. Springer, June 2008. See [CGK11] for the journal version. See [CGK08a] for the TR version. Slides available here.

  7. 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.

  8. Pierre Fraigniaud and Cyril Gavoille. Polylogarithmic network navigability using compact metrics with small stretch. In 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 62–69. ACM Press, June 2008.

  9. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Construction locale de sous-graphes couvrants peu denses. In 10es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 105–108, May 2008. Slides available here. See [DGPV08] for the TR version.

  10. Cyril Gavoille. On sparse spanners. In ANR Aladdin Meeting, May 2008.

  11. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed sparse spanner construction. Research Report RR-1441-08, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2008. Original URL. See [DGPV08b] for the conference version.

  12. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theoretical Computer Science, 399(1-2):83–100, February 2008. See [DG06] for the conference version.

  13. Cyril Gavoille and Nicolas Hanusse. On compact encoding of pagenumber k graphs. Discrete Mathematics & Theoretical Computer Science, 10(3):23–34, January 2008.


2007

  1. Cyril Gavoille and Arnaud Labourel. Distributed relationship schemes for trees. In 18th Annual International Symposium on Algorithms and Computation (ISAAC), volume 4835 of Lecture Notes in Computer Science, pages 728–738. Springer, December 2007. See [GL07a] for a brief announcement. Slides available here.

  2. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Łukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Research Report RR-1440-07, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2007. Original URL. See [GKKN07] for a brief announcement. See [GKKKN09] for the journal version.

  3. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Łukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Research Report 6399, INRIA, December 2007. See [GKKN07] for a brief announcement. See [GKKKN09] for the journal version.

  4. Cyril Gavoille and Arnaud Labourel. Schéma relationnel distribué pour les arbres. In 9es Journées Graphes et Algorithmes, page 19, November 2007. Slides available here.

  5. Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In Lars Arge and Emo Welzl, editors, 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 582–593. Springer, October 2007. Slides available here.

  6. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In 21st International Symposium on Distributed Computing (DISC), volume 4731 of Lecture Notes in Computer Science, pages 179–192. Springer, September 2007. Slides available here.

  7. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Brief announcement: On the complexity of distributed greedy coloring. In 21st International Symposium on Distributed Computing (DISC), volume 4731 of Lecture Notes in Computer Science, pages 482–484. Springer, September 2007. Slides available here. See [GKKKN07] for an updated version and [GKKKN07b].

  8. Yon Dourisboure, Feodor F. Dragan, Cyril Gavoille, and Chenyu Yan. Spanners for bounded tree-length graphs. Theoretical Computer Science, 383(1):34–44, September 2007. A preliminary version appears as RR-1316-04 (2004) and in SIROCCO '04.

  9. Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and David Andrew Twigg. Forbidden-set labeling on graphs. In 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), August 2007. Co-located with PODC 2007, Slides available here.

  10. Cyril Gavoille and Arnaud Labourel. Brief annoucement: On local representation of distances in trees. In 26th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 246–247. ACM Press, August 2007. See [GL07b] for the full version. Slides available here.

  11. Cyril Gavoille. Localized data structures (keynote talk). In 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), August 2007. Co-located with PODC 2007, See web pages here.

  12. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: Information sensitivity of graph coloring. In 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of Lecture Notes in Computer Science, pages 231–242. Springer, July 2007. See [FGIP09] for the journal version.

  13. 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.

  14. Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, and Zvi Lotker. Universal augmentation schemes for network navigability: Overcoming the √n-barrier. In 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1–7. ACM Press, June 2007. BEST PAPER AWARD. Slides available here. See [FGKLL09] for the journal version.

  15. 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.

  16. Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, and Zvi Lotker. A propos des schémas d'augmentation universels pour la navigation dans les réseaux. In 9es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 23–26, May 2007. See [FGKLL09] for the journal version.

  17. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. In 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, volume 28 of Electronic Notes in Discrete Mathematics, pages 153–160. Elsevier, March 2007. Dedicated to Jarik Nešetřil on the occasion of his 60th birthday, Correction for Caterpillars here.

  18. 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.

  19. 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).

  20. Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008–2029, 2007. Extended abstract published in EUROCOMB '03. Appears also as RR-1326-01 (2004).


2006

  1. 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.

  2. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Schéma d'adjacence compact pour les arbres de degrés borné. In 8es Journées Graphes et Algorithmes, November 2006. Slides available here.

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

  4. Cyril Gavoille. Distributed data structures: A survey on informative labeling schemes (invited talk). In Rastislav Královič and Paweł Urzyczyn, editors, 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 4162 of Lecture Notes in Computer Science, page 38. Springer, August 2006.

  5. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. In 13th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 4056 of Lecture Notes in Computer Science, pages 100–114. Springer, July 2006. See [DG08] for the journal version. Appears also as RR-1388-06 (2006). Slides available here.

  6. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. In 13th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 4056 of Lecture Notes in Computer Science, pages 143–156. Springer, July 2006. Appears also as RR-1389-06 (2006). Correction for Caterpillars here.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. Pierre Fraigniaud and Cyril Gavoille. Header-size lower bounds for end-to-end communication in memoryless networks. Computer Networks, 50(10):1630–1638, July 2006. Selected paper for the DISC '03 Special Issue.

  12. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. Research Report RR-1389-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2006. Original URL. Extended abstract published in SIROCCO '06. Correction for Caterpillars here.

  13. 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.

  14. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks even small worlds. Distributed Computing, 18(4):279–291, March 2006. Appears also in PODC '04.

  15. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Research Report RR-1388-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2006. Original URL. Extended abstract published in SIROCCO '06.

  16. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. Graphs and Combinatorics, 22(2):185–202, 2006. Extended abstract published in WG '04.


2005

  1. 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.

  2. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. In 16th Annual International Symposium on Algorithms and Computation (ISAAC), volume 3827 of Lecture Notes in Computer Science, pages 1122–1131. Springer, December 2005. See [BG09] for the journal version.

  3. Cyril Gavoille and Olivier Ly. Distance labeling in hyperbolic graphs. In 16th Annual International Symposium on Algorithms and Computation (ISAAC), volume 3827 of Lecture Notes in Computer Science, pages 1071–1079. Springer, December 2005. Slides available here.

  4. 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.

  5. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Edge partition of toroidal graphs into forests in linear time. In 7th International Colloquium on Graph Theory (ICGT), volume 22 of Electronic Notes in Discrete Mathematics, pages 421–425. Elsevier, October 2005. Slides available here.

  6. Fabrice Bazzaro and Cyril Gavoille. Distance labeling for permutation graphs. In 7th International Colloquium on Graph Theory (ICGT), volume 22 of Electronic Notes in Discrete Mathematics, pages 461–467. Elsevier, October 2005. Slides available here. See [BG09] for the journal version.

  7. 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.

  8. Cyril Gavoille. Distributed data structures: A survey I & II. In 8th Seminar on Optimization and Decision Aid (SODA), France Télécom R&D Division, June 2005. See the program here.

  9. Cyril Gavoille. Distributed data structures: A survey (invited talk). In 12th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 3499 of Lecture Notes in Computer Science, page 2. Springer, May 2005. Slides available here.

  10. Cyril Gavoille. Étiquetage des graphes. In École Jeunes Chercheurs en Algorithmique et Calcul Formel - École thématique CNRS 05 13 051, April 2005. See http://www.lirmm.fr/~ejc2005.

  11. 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).

  12. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Research Report RR-1343-05, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2005. Original URL.

  13. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. Journal of Graph Algorithms and Applications, 9(2):185–204, 2005. Appears also as RR-1295-03 (2003).


2004

  1. Frédéric Ferchaud, Vu Duong, Cyril Gavoille, and Mohamed Mosbah. Reducing disturbances by using absorption areas. In 1st International Conference on Research in Air Transportation (ICRAT), pages 111–115, November 2004.

  2. Fabrice Bazzaro and Cyril Gavoille. Étiquetage de distance des graphes de permutation. In E. Duchène and Sylvain Gravier, editors, 6es Journées Graphes et Algorithmes, pages 22–24. Les Cahiers du laboratoire Leibniz, No 114, October 2004.

  3. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85–112, October 2004. See [GPPR00] for the TR version. See [GPPR01] for the conference version.

  4. Frédéric Ferchaud, Vu Duong, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In 23rd IEEE International Digital Avionics Systems Conference (DASC), volume 1, pages 2.A.3–1–2.A.3–6, October 2004.

  5. 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).

  6. Vu Duong, Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. A new slot allocation for ATFM. In 7th IEEE International Conference on Intelligent Transportation Systems (ITSC), pages 1075–1079, October 2004.

  7. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. Research report, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2004. Original URL. Extended abstract published in WG '04. Appears also as Graphs and Combinatorics.

  8. 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.

  9. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks even small worlds. In 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 169–178. ACM Press, July 2004. Appears also in Distributed Computing for the PODC '04 Special Issue. Appears also as LRI-1376 (2003).

  10. 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.

  11. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. In 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 3353 of Lecture Notes in Computer Science, pages 270–284. Springer, June 2004. A revised version is available as RR-1333-04. Appears also as Graphs and Combinatorics.

  12. Yon Dourisboure and Cyril Gavoille. Sparse additive spanners for bounded tree-length graphs. In 11th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 3104 of Lecture Notes in Computer Science, pages 123–137. Springer, June 2004. See [DDGY07] for the journal version. Appears also as RR-1316-04 (2004).

  13. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory of Computing Systems, 37(3):441–456, May 2004. Appears also as IT-C Series 2001-6 (2001), and an extended abstract appears in SPAA '02.

  14. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclectisme dans les petits mondes. In 6es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2004. Slides available here. Apparaît aussi dans LRI-1376 (2003).

  15. Yon Dourisboure and Cyril Gavoille. Small diameter bag tree-decompositions. Research Report RR-1326-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2004. Original URL. An updated version appears in Discrete Mathematics. Appears also as EUROCOMB '03.

  16. Yon Dourisboure and Cyril Gavoille. Sparse additive spanners for bounded tree-length graphs. Research Report RR-1316-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2004. Original URL. An extended abstract appears in SIROCCO '04.

  17. Richard Castanet, Cyril Gavoille, Mohamed Mosbah, and Frédéric Ferchaud. Utilisation des zones d'absorption pour améliorer la gestion de flux du trafic aérien. Rapport de contrat (intermédiaire) marché C/1.291/CE/NB/03/ - EUROCONTROL - ADERA, LaBRI, Université Bordeaux 1 - ENSEIRB, January 2004.

  18. Cyril Gavoille. Routage avec indépendance des noms. In ACI PairApair Meeting, January 2004.


2003

  1. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115–130, December 2003. See [GP01a] for the conference version. See [GP01c] for the TR version.

  2. Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In ERC Innovative Research Workshop, December 2003.

  3. Richard Castanet, Cyril Gavoille, Mohamed Mosbah, and Frédéric Ferchaud. Gestion de flux du traffic aérien en intra et inter réseaux : un modèle de graphes évolutifs. Rapport de contrat (final) marché C20135E/DM/02 - EUROCONTROL, LaBRI, Université Bordeaux 1 - ENSEIRB, November 2003.

  4. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks the world. Research Report LRI-1376, LRI, Université Paris-Sud, 91405 Orsay cedex, France, October 2003. Extended abstract published in PODC '04.

  5. Pierre Fraigniaud and Cyril Gavoille. Lower bounds for oblivious single-packet end-to-end communication. In 17th International Symposium on Distributed Computing (DISC), volume 2848 of Lecture Notes in Computer Science, pages 211–223. Springer, October 2003. Appears also as RR-1289-03 (2003), and a revised version appears in Computer Networks.

  6. Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Computing, 16(2-3):111–120, September 2003. PODC 20-Year Special Issue, See [GP01b] for the TR version.

  7. Cyril Gavoille and Christophe Paul. Optimal distance labeling schemes for interval and circular-arc graphs. In Giuseppe di Battista and Uri Zwick, editors, 11th Annual European Symposium on Algorithms (ESA), volume 2832 of Lecture Notes in Computer Science, pages 254–265. Springer, September 2003. See [GP08] for the journal version. See [GP03a] for the TR version. Slides available here.

  8. 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.

  9. Yon Dourisboure and Cyril Gavoille. Tree-decomposition of graphs with small diameter bags. In J. Fila, editor, 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 100–104, September 2003. An updated version appears in Discrete Mathematics.

  10. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. In 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2880 of Lecture Notes in Computer Science, pages 81–92. Springer-Verlag, June 2003. Appears also as RR-1295-03 (2003), and an updated version appears in Journal of Graph Algorithms and Applications (2005).

  11. 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.

  12. 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.

  13. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. Research Report RR-1295-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 WG '03, and an updated version appears in Journal of Graph Algorithms and Applications (2005).

  14. 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.

  15. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. An information-theoretic upper bound of planar graphs using triangulation. In 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2607 of Lecture Notes in Computer Science, pages 499–510. Springer, February 2003. See [BGH11] for the journal version. Appears also as RR-1279-02 (2002). Slides available here.

  16. Cyril Gavoille and Christophe Paul. Small universal distance matrices. Research Report RR-1290-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2003. Original URL. See [GP03] for the conference version. See [GP08] for the journal version.

  17. Pierre Fraigniaud and Cyril Gavoille. Lower bounds for oblivious single-message end-to-end communication. Research Report RR-1289-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2003. Original URL. An extended abstract appears in DISC '03, and a revised version appears in Computer Networks.

  18. 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

  1. 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).

  2. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. An information upper bound of planar graphs using triangulation. Research Report RR-1279-02, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2002. Original URL. See [BGH11] for the journal version. Extended abstract published in STACS '03.

  3. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: A survey and a new distributed algorithm. In 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 258–264. ACM Press, August 2002. Appears also as IT-C Series 2001-6 (2001), and in Theory of Computing Systems. Slides available here.

  4. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing Knödel graphs. Discrete Mathematics, 250(1-3):41–62, May 2002. Extended abstract published in WG '99. Appears also as RR-LRI-1238 (2000).

  5. 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.

  6. Cyril Gavoille. À propos du nombre de graphes planaires. In GT Combinatoire et Algorithmique, April 2002.

  7. 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

  1. Cyril Gavoille. A note on implicit representation of graphs. Research Report RR-1268-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2001. Original URL. See here for a pdf.

  2. Cyril Gavoille and Christophe Paul. Split decomposition and distance labelling: An optimal scheme for distance hereditary graphs. In Jaroslav Nešetřil, Marc Noy, and Oriol Serra, editors, European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), volume 10 of Electronic Notes in Discrete Mathematics, pages 117–120, November 2001. For a version with references, click here. See [GP03b] for the journal version. See [GP01c] for the TR version.

  3. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Research Report RR-1263-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 2001. Original URL. See [GP03b] for the journal version. See [GP01a] for the conference version.

  4. 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.

  5. Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Research Report RR-1261-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, August 2001. Original URL. See [GP03c] for the journal version.

  6. Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. In Friedhelm Meyer auf der Heide, editor, 9th Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science, pages 476–487. Springer, August 2001. See [GKKPP00] for the TR version.

  7. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Identifying nearest common ancestors in a distributed environment. Technical Report IT-C Series 2001-6, ISSN 1600-6100, The IT University of Copenhagen, August 2001. Extended abstract published in SPAA '02, and in Theory of Computing Systems.

  8. 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).

  9. 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.

  10. 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.

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

  12. 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.

  13. 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.

  14. 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.

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

  16. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. In 12th Symposium on Discrete Algorithms (SODA), pages 210–219. ACM-SIAM, January 2001. See [GPPR00] for the TR version. See [GPPR04] for the journal version. Slides available here.

  17. 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.

  18. 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.

  19. 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

  1. Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. Research Report RR-1250-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2000. Original URL. See [GKKPP01] for the conference version.

  2. 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.

  3. Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, and John Michael Robson. On recognizing Cayley graphs. In 8th Annual European Symposium on Algorithms (ESA), volume 1879 of Lecture Notes in Computer Science, pages 76–87. Springer, September 2000. Appears also as LRI-1242 (2000).

  4. 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.

  5. Cyril Gavoille and Christophe Paul. Approximate distance labeling schemes. In 6th International Colloquium on Graph Theory (ICGT), volume 5 of Electronic Notes in Discrete Mathematics, pages 134–137. Elsevier, July 2000. Slides available here.

  6. 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).

  7. 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.

  8. Cyril Gavoille. Implicit representation and distance labeling of graphs. In Workshop on Structured Families of Graphs, May 2000.

  9. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. Research Report RR-1239-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, April 2000. Original URL. See [GPPR04] for the journal version. See [GPPR01] for the conference version.

  10. 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.

  11. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing Knödel and Fibonacci graphs. Research Report LRI-1238, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. An updated version appears in Discrete Mathematics. Extended abstract published in WG '99.

  12. Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Recognizing abelian Cayley colored digraphs. Research Report LRI-1242, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. Extended abstract of the updated version published in ESA '00.

  13. Cyril Gavoille. On the dilation of interval routing. The Computer Journal, 43(1):243–249, 2000. See [Gav96c] for the TR version.

  14. 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

  1. 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.

  2. 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.

  3. Cyril Gavoille, Jean-Claude Bermond, and André Raspaud. Proceedings of the 6th international colloquium on structural information & communication complexity, sirocco 6. Carleton Scientific, July 1999. Abstract and table of contents available here.

  4. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing bipartite incident-graphs of circulant digraphs. In Peter Widmayer, Gabriele Neyer, and Stephan Eidenbenz, editors, 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1665 of Lecture Notes in Computer Science, pages 215–227. Springer, June 1999. An updated version appears in Discrete Mathematics. Appears also as RR-LRI-1238 (2000). Slides from "2e journée Graphes et Algorithmes à Orléans, avril 1999" available here.

  5. 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.

  6. 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.

  7. Cyril Gavoille. Tables compactes de routage pour graphe de genre borné. In Séminaire du Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), 1999.


1998

  1. 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.

  2. 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.

  3. 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.

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

  5. 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.

  6. 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.

  7. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

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

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


1996

  1. Cyril Gavoille. Routage compact. In Séminaire du LaBRI, November 1996.

  2. 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.

  3. 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.

  4. 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.

  5. 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).

  6. 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.

  7. 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.

  8. 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.

  9. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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

  1. Frédéric Desprez, Cyril Gavoille, Bruno Jargot, and Makan Pourzandi. Tests des performances des communications de la machine Volvox IS-860. La lettre du Transputer et des Calculateurs Parallèles, 19:11–35, October 1993. Updated version of TR93-02 (1993).

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

  3. Frédéric Desprez, Cyril Gavoille, Bruno Jargot, and Makan Pourzandi. Tests des performances des communications de la machine Volvox IS-860. Technical Report 93-02, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, March 1993. Appears also as La Lettre du Transputeur.


1992

  1. Cyril Gavoille. Evaluation of the MasPar MP-1 performances. Technical Report 92-01, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, February 1992. Original URL.


Co-authors (133)

 22. Abraham, Ittai                2. Goldberg, Andrew V.           1. Ochem, Pascal              
  1. Abramsky, Samson              1. Gossa, Julien                 1. Odak, Saeed                
  5. Alstrup, Stephen              2. Groenland, Carla              1. Patt-Shamir, Boaz          
  2. Barenboim, Leonid             3. Gupta, Anupam                13. Paul, Christophe           
  1. Barillot, Christian           3. Guévremont, Eric              3. Pelc, Andrzej              
  2. Barrière, Lali                2. Halftermeyer, Pierre         26. Peleg, David               
  2. Baucher, Edgar                2. Halvorsen, Esben Bistrup      6. Perković, Ljubomir         
  5. Bazzaro, Fabrice             29. Hanusse, Nicolas              2. Petersen, Holger           
  1. Beaudouin-Lafon, Michel       1. Herzig, Andreas               1. Picavet, Timothé           
  1. Bermond, Jean-Claude          5. Hilaire, Claire               4. Pilipczuk, Michał          
  3. Biniaz, Ahmad                11. Ilcinkas, David               3. Poulalhon, Dominique       
  4. Bonamy, Marthe                3. Jacques, Amaury               2. Pourzandi, Makan           
 25. Bonichon, Nicolas             2. Jargot, Bruno                 1. Pykacz, Jarosław           
  3. Bose, Prosenjit               3. Joret, Gwenaël                8. Pérennès, Stéphane         
  1. Cani, Marie-Paule             1. Kachigar, Ghazal              1. Queinnec, Isabelle         
  2. Castanet, Richard             6. Kanté, Mamadou Moustapha      3. Raspaud, André             
  2. Casteigts, Arnaud             3. Kaplan, Haim                  3. Rauhe, Theis               
  1. Censor-Hillel, Keren          2. Katz, Michal                  3. Raz, Ran                   
  1. Chaumette, François           2. Katz, Nir A.                  1. Robson, John Michael       
  3. Chechik, Shiri                1. Kirchner, Claude              3. Schaeffer, Gilles          
  3. Cohen, Johanne                4. Klasing, Ralf                 1. Scheideler, Christian      
  1. Conreur, Gérald              10. Kosowski, Adrian              1. Seinturier, Lionel         
  1. Cortier, Véronique            1. Krivine, Jean                 3. Smid, Michiel              
  6. Courcelle, Bruno              3. Kuszner, Łukasz               1. Sommer, Christian          
  3. de Carufel, Jean-Lou         10. Labourel, Arnaud              2. Sopena, Eric               
  8. Derbel, Bilel                 1. Lamarre, Philippe             1. Spirakis, Paul G.          
  2. Desprez, Frédéric             1. Lamnabhi, Françoise           3. Talwar, Kunal              
  6. Dieng, Youssou                3. Lebhar, Emmanuelle            1. Tellier, Isabelle          
  5. Diot, Émilie                  1. Letournel, Anne-Catherine     2. Thorup, Mikkel             
  9. Dourisboure, Yon              3. Lotker, Zvi                   1. Théoleyre, Fabrice         
  1. Dragan, Feodor F.             1. Ly, Olivier                   1. Torres, Serge              
  2. Dross, François               3. Maheshwari, Anil              1. Touzet, Hélène             
  3. Dujmović, Vida                1. Majorczyk, Frédéric           1. Truchet, Charlotte         
  3. Duong, Vu                    13. Malkhi, Dahlia                1. Tsoukias, Alexandros       
  4. Eilam, Tamar                  5. Mans, Bernard                 3. Twigg, David Andrew        
  2. Elkin, Michael                3. Markiewicz, Marcin            1. Tylec, Tomasz              
  5. Esperet, Louis                1. Marthe, Bonamy                1. Verleysen, Michel          
  6. Ferchaud, Frédéric            1. Meyer auf der Heide, Friedh   9. Viennot, Laurent           
  1. Fijalkow, Inbar               3. Micek, Piotr                  1. Wesolek, Alexandra         
 38. Fraigniaud, Pierre            3. Morin, Pat                    3. Wieder, Udi                
  3. Gengler, Marc                 6. Mosbah, Mohamed               1. Yan, Chenyu                
  1. Gilbert, Seth                 4. Navarra, Alfredo              3. Zemmari, Akka              
  5. Glacet, Christian             4. Nehéz, Martin                 1. Zémor, Gilles              
  5. Godfroy, Quentin              3. Neiman, Ofer                                                
  1. Gogniat, Guy                  2. Nisan, Noam
21 décembre 2024 (299)
[My home page]