Cyril GAVOILLE
List of Publications (exhaustive)

(bibtex format)
Compact routing papers
Co-authors
[My biblio]
[My home page]
[Publications of the Lab.]

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.

2017

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

  2. Cyril Gavoille. Beyond classical local models in distributed computing. In 44th École de Printemps en Informatique Théorique (EPIT) -- Distributed Computing, May 2017. See http://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. Journal of Computational Geometry, 8(1), 2017.



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, 27nd Annual International Symposium on Algorithms and Computation (ISAAC), pages 19:1-19:14. LIPIcs, December 2016.

  2. Cyril Gavoille and David Ilcinkas. Proceedings of the 30th International Symposium on Distributed Computing, DISC 2016, Paris, France, September 27-29, 2016. 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, 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 17èmes 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 L_1- and L_\infty-Delaunay triangulations. Computational Geometry, 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 15èmes 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 L_1- and L_\infty-Delaunay triangulations. In L. Epstein and P. 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 L_1- 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 14èmes 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 L_1- 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. Book available here.

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

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

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

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

  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. Émilie Diot and Cyril Gavoille. La hiérarchie des graphes k-chemin séparables. In 12èmes Journées Graphes et Algorithmes, page 7, November 2010. Slides available here.

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

  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. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Spanners additifs de taille sous-quadratique pour les graphes orientés. In 12èmes Journées Graphes et Algorithmes, page 9, 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. 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 12èmes 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. Long version available here.

  13. Cyril Gavoille, Quentin Godfroy, and Laurent Viennot. Graphes de recouvrement multichemins. In 12èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), volume inria-00475970. HAL, June 2010. Long version available here.

  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. Émilie Diot and Cyril Gavoille. On the path separability of planar graphs. In Elsevier, editor, European Conference on Combinatorics, Graph Theory and Applications (EuroComb), volume 34, pages 549-552. Electronic Notes in Discrete Mathematics, September 2009.

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

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

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

  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 11èmes 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 \sqrtn-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 10èmes 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 K_2,4. In 10èmes 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, pages 151-155. Electronic Notes in Discrete Mathematics, 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, 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 10èmes 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, 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 9èmes 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. 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.

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

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

  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 \sqrtn-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 9èmes 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 9èmes 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 Elsevier, editor, 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, volume 28, pages 153-160. Electronic Notes in Discrete Mathematics, March 2007. Dedicated to Jarik Nesetril 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. 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).

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



2006

  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 8èmes 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 R. Královic and P. 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. 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. See [AGGM05] for the TR version. Slides available here: .ppt and .pdf.

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

  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 Elsevier, editor, 7th International Conference on Graph Theory (ICGT), volume 22, pages 421-425. Electronic Notes in Discrete Mathematics, October 2005. Slides available here.

  6. Fabrice Bazzaro and Cyril Gavoille. Distance labeling for permutation graphs. In Elsevier, editor, 7th International Conference on Graph Theory (ICGT), volume 22, pages 461-467. Electronic Notes in Discrete Mathematics, 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. Program.

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

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

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



2004

  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. Etiquetage de distance des graphes de permutation. In E. Duchène et S. Gravier, editor, 6èmes Journées Graphes et Algorithmes, pages 22-24. Les Cahiers du laboratoire Leibniz, No 114, October 2004.

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

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

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

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

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

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

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

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

  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 6èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2004. Slides available here. Appara&\circ;it aussi dans LRI-1376 (2003).

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

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

  17. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Appears also as RR-1239-00 (2000), and in SODA '01. Another link is available here.

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



2003

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

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

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

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

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

  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, Appears also as RR-1261-01 (2001).

  7. Cyril Gavoille and Christophe Paul. Optimal distance labeling schemes for interval and circular-arc graphs. In G. di Battista and U. 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. Appears also as RR-1290-03 (2003). 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. A revised appears in Theoretical Computer Science.

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

  10. 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. Appears also as RR-1294-03 (2003), and a revised appears in Theoretical Computer Science.

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

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

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

  14. 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 [BGH10] for the journal version. Appears also as RR-1279-02 (2002). Slides available here.

  15. 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. An extended abstract appears in ESA '03. See [GP08] for the journal version.

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

  17. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. Extended abstract published in COMB '01. Appears also as RR-1263-01 (2001).

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



2002

  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 [BGH10] 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. 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.

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

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



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 Marc Noy Jaroslav Nesetril and Oriol Serra, editors, European Conference on Combinatorics, Graph Theory and Applications (EuroComb), volume 10, pages 117-120. Electronic Notes in Discrete Mathematics, November 2001. For a version with references, click here. A long version appears in Discrete Mathematics, and also as RR-1263-01 (2001).

  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. An updated version appears in Discrete Mathematics, and an extended abstract appears in COMB '01.

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

  6. 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. Appears also in Distributed Computing for the PODC 20-Year Special Issue.

  7. Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. In F. 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. Appears also as RR-1250-00 (2000).

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

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

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

  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. Appears also as RR-1239-00 (2000), and an updated version appears in Journal of Algorithms. 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. Extended abstract published in DISC '98. Appears also as RR-1202-98 (1998).

  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. Updated version of RR-1181-97 (1997).

  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. Extended abstract published in ESA '01.

  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 and Christophe Paul. Approximate distance labeling schemes. In Elsevier, editor, 6th International Conference on Graph Theory (ICGT), volume 5, pages 134-137. Electronic Notes in Discrete Mathematics, July 2000. Slides available here.

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

  6. 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. Extended abstract of RR-1233-00 (2000). An updated version is available in Journal of Discrete Algorithms. Slides available here.

  7. 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. An updated version appears in Journal of Algorithms, and an extended abstract appears in SODA '01.

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

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

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

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

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

  13. 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. Updated version of RR-1176-97 (1997).

  2. Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Jir&\acute;i 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. Extended abstract of RR-1213-99 (1999), and a revised version is available here.

  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ère Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1-5. INRIA, May 1999. Appara&\circ;it aussi dans RR-1213-99 (1999).

  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. Extended abstract published in ICALP '99, and a revised version is available here.



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. An updated version appears in SIAM J. on Computing. Appears also as RR-1202-98 (1998). 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. Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. Research Report RR-1202-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, April 1998. Original URL. Extended abstract published in DISC '98, and a revised version appears in SIAM J. on Computing.

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

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

  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. Extended abstract published in SIROCCO '97. Appears also in JPDC.

  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. An updated version appears in TCS, 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. An updated version appears in SIAM Journal on Discrete Mathematics.

  4. Cyril Gavoille. On the dilation of interval routing. In Igor Pr&\acute;ivara and Peter Ruzicka, 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. Appears also as RR-1145-96 (1996).

  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. Appears also as RR-1181-97 (1997).

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

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

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

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

  5. 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. Appears also as RR95-46 (1995) and I3S 95-37 (1995).

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

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

  8. 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. Extended abstract published in PODC '96.

  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. Extended abstract published in PODC '96.

  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. An updated version appears in Journal of Algorithms.



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, 6èmes 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 (89)

 21. Abraham, Ittai                3. Guévremont, Eric             1. Patt-Shamir, Boaz          
  1. Abramsky, Samson              2. Halftermeyer, Pierre         13. Paul, Christophe           
  5. Alstrup, Stephen              2. Halvorsen, Esben Bistrup      2. Pelc, Andrzej              
  2. Barenboim, Leonid            26. Hanusse, Nicolas             25. Peleg, David               
  2. Barrière, Lali              11. Ilcinkas, David               6. Perković, Ljubomir        
  5. Bazzaro, Fabrice              2. Jargot, Bruno                 2. Petersen, Holger           
  1. Bermond, Jean-Claude          6. Kanté, Mamadou Moustapha     3. Poulalhon, Dominique       
  2. Biniaz, Ahmad                 3. Kaplan, Haim                  2. Pourzandi, Makan           
 22. Bonichon, Nicolas             2. Katz, Michal                  1. Pykacz, Jarosław          
  2. Bose, Prosenjit               2. Katz, Nir A.                  8. Pérennès, Stéphane      
  2. Castanet, Richard             1. Kirchner, Claude              3. Raspaud, André            
  3. Chechik, Shiri                4. Klasing, Ralf                 3. Rauhe, Theis               
  3. Cohen, Johanne               10. Kosowski, Adrian              3. Raz, Ran                   
  6. Courcelle, Bruno              3. Kuszner, Łukasz              1. Robson, John Michael       
  8. Derbel, Bilel                 9. Labourel, Arnaud              3. Schaeffer, Gilles          
  2. Desprez, Frédéric           3. Lebhar, Emmanuelle            1. Scheideler, Christian      
  5. Dieng, Youssou                3. Lotker, Zvi                   2. Smid, Michiel              
  5. Diot, Émilie                 1. Ly, Olivier                   1. Sommer, Christian          
  9. Dourisboure, Yon              2. Maheshwari, Anil              2. Sopena, Eric               
  1. Dragan, Feodor F.             1. Majorczyk, Frédéric         1. Spirakis, Paul G.          
  3. Duong, Vu                    13. Malkhi, Dahlia                2. Talwar, Kunal              
  4. Eilam, Tamar                  5. Mans, Bernard                 2. Thorup, Mikkel             
  2. Elkin, Michael                3. Markiewicz, Marcin            3. Twigg, David Andrew        
  6. Ferchaud, Frédéric          1. Meyer auf der Heide, Friedh   1. Tylec, Tomasz              
 37. Fraigniaud, Pierre            6. Mosbah, Mohamed               9. Viennot, Laurent           
  3. Gengler, Marc                 4. Navarra, Alfredo              3. Wieder, Udi                
  5. Glacet, Christian             4. Nehéz, Martin                1. Yan, Chenyu                
  5. Godfroy, Quentin              2. Neiman, Ofer                  3. Zemmari, Akka              
  2. Goldberg, Andrew V.           2. Nisan, Noam                   2. de Carufel, Jean-Lou       
  2. Gupta, Anupam                 1. Ochem, Pascal                                               

21 novembre 2017 (248)
[My home page]