Graphs & Applications
Publications of Cyril GAVOILLE
(bibtex format)
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,
© Ideal,
© King's College.
[
2007 |
2006 |
2005 |
2004 |
2003 |
2002 |
2001 |
2000 |
1999 |
1998 |
1997 |
1996 |
1995 |
1994 |
1993 |
1992]
2007
- 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.
- Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz 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. See [GKKN07] for a brief announcement.
- Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz 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.
- 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.
- 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.
- 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.
- 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.
- 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].
- Bruno Courcelle, Cyril Gavoille, Mustapha 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.
- 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.
- 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.
- 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.
- 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.
- 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 [AGMW06] for the TR version. See here for a long version.
- 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.
- Youssou Dieng and Cyril Gavoille. Routage dans les graphes cellulaires. In 9èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 91-94, May 2007.
- Cyril Gavoille. An overview on compact routing. In Workshop on Peer-to-Peer, Routing in Complex Graphs, and Network Coding, March 2007. See web pages here.
- Tamar Eilam, Cyril Gavoille, and David Peleg. Average stretch analysis of compact routing schemes. Discrete Applied Mathematics, 155:598-610, January 2007. Appears also as RR-1195-98 (1998).
- 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).
- Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theoretical Computer Science, 2007. To appear, see [DG06] for the conference version.
- Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 2007. to appear, See [BG05b] for the conference version.
- Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM Journal on Discrete Mathematics, 2007. To appear, see [GP03] for the conference version.
2006
- Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strongly-bounded sparse decompositions of minor free graphs. Technical Report MSR-TR-2006-192, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2006. See [AGMW07] for the conference version.
- Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Schéma d'étiquetage d'adjacence pour les arbres de degrés borné. In 8èmes Journées Graphes et Algorithmes, November 2006.
- Cyril Gavoille. An overview on compact routing. In 2nd Research Workshop on Flexible Network Design, October 2006. See web pages here.
- 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.
- 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.
- 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.
- 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.
- 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 [DG07b] for the journal version. Appears also as RR-1388-06 (2006). Slides available here.
- 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).
- Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Adjacency labeling for bounded degree trees and applications. In 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, July 2006. Dedicated to Jarik Nesetril on the occasion of his 60th birthday.
- 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.
- 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.
- 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.
- 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. Extended abstract published in SIROCCO '06.
- 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. Extended abstract published in PODC '06.
- 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. Extended abstract published in SIROCCO '06.
- 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
- 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 [BG07] for the journal version.
- 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.
- 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.
- 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.
- 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.
- 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, and See [BG07] for the journal version.
- Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442-456. Springer, September 2005. Slides available here.
- Cyril Gavoille. 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.
- 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.
- 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.
- 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.
- 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).
- 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).
- Cyril Gavoille and Nicolas Hanusse. On compact encoding of pagenumber k graphs. Discrete Mathematics & Theoretical Computer Science, 2005. To appear.
2004
- 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.
- Vu Duong, Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In 23rd IEEE International Digital Avionics Systems Conference (DASC), October 2004.
- 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.
- 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).
- 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.
- 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. Extended abstract published in WG '04. Appears also as Graphs and Combinatorics.
- 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 Journal of Distributed Computing for the PODC '04 Special Issue. Appears also as LRI-1376 (2003).
- 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. Extended abstract published in DISC '04.
- Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. In 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 20-24. ACM Press, July 2004. Updated version here, and slides available here.
- 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).
- 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. Springer, June 2004. 270-284, A revised version is available as RR-1333-04. Appears also as Graphs and Combinatorics.
- 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. Apparaît aussi dans LRI-1376 (2003).
- 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. An updated version appears in Discrete Mathematics. Appears also as EUROCOMB '03.
- 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. An extended abstract appears in SIROCCO '04.
- 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/, LaBRI, Université Bordeaux 1 - ENSEIRB, January 2004.
- 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.
- 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:441-456, 2004. Appears also as IT-C Series 2001-6 (2001), and an extended abstract appears in SPAA '02.
2003
- Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In ERC Innovative Research Workshop, December 2003.
- 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, November 2003.
- 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.
- 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.
- 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.
- 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 [GP07] for the journal version. Appears also as RR-1290-03 (2003). Slides available here.
- 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.
- 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).
- 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. Appears also as RR-1294-03 (2003), and a revised appears in Theoretical Computer Science.
- Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Computing, 16:111-120, May 2003. PODC 20-Year Special Issue, Appears also as RR-1261-01 (2001).
- 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. An extended abstract appears in WG '03, and an updated version appears in Journal of Graph Algorithms and Applications (2005).
- 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. An extended abstract appears in SIROCCO '03, and a revised appears in Theoretical Computer Science.
- 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. An extended abstract appears in DISC '03, and a revised version appears in Computer Networks.
- 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. Appears also as RR-1279-02 (2002), and a revised version is available here. Slides available here.
- 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. An extended abstract appears in ESA '03. A revised version is available here.
- 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).
- Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Journal of Discrete Algorithms, 1(2):237-254, 2003. Extended abstract published in SIROCCO '00. Appears also as RR-1233-00 (2000).
- 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).
2002
- Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. In 16th International Symposium on Distributed Computing (DISC), volume 2508 of Lecture Notes in Computer Science, pages 252-264. Springer, October 2002. An updated version is available here. Appears also as RR-1274-02 (2002).
- 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. Extended abstract published in STACS '03, and a revised version is available here.
- 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.
- 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. Extended abstract published in DISC '02.
- Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2285 of Lecture Notes in Computer Science, pages 65-75. Springer, March 2002. Slides available here.
- 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
- 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.
- 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 (COMB), 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).
- 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. An updated version appears in Discrete Mathematics, and an extended abstract appears in COMB '01.
- 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. Extended abstract published in STACS '02.
- 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. Appears also in Journal of Distributed Computing for the PODC 20-Year Special Issue.
- 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.
- 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-488. Springer, August 2001. Appears also as RR-1250-00 (2000).
- Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. Distributed Computing, 14:217-229, July 2001. Extended abstract published in PODC '00. Appears also as LRI-1241 (2000).
- Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, 28th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757-772. Springer, July 2001. Slides available here.
- Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating sets in planar graphs with applications. In 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2204 of Lecture Notes in Computer Science, pages 201-216. Springer, June 2001. A revised version is available here.
- Cyril Gavoille. Compact and distributed data structures (invited lecture). In IWIN-SIROCCO '01 joint conference, June 2001. Slides available here.
- Pierre Fraigniaud and Cyril Gavoille. Comment router dans un arbre ?. In 3èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 85-88. INRIA, May 2001. Slides available here.
- Yon Dourisboure and Cyril Gavoille. Interval routing for generalized Hypercube-like graphs. In 3èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 61-68. INRIA, May 2001.
- Cyril Gavoille, 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. Extended abstract published in WG '01, and a revised version is available here.
- Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column, 32(1):36-52, March 2001.
- 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. Extended abstract published in ICALP '01.
- 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.
- Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. SIAM Journal on Computing, 31(3):706-721, 2001. Extended abstract published in DISC '98. Appears also as RR-1202-98 (1998).
- Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61(5):679-687, 2001. Updated version of RR-1181-97 (1997).
2000
- 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. Extended abstract published in ESA '01.
- 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.
- 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).
- Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. In 19th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, July 2000. The full version appears in JDC. Appears also as LRI-1241 (2000).
- Cyril Gavoille and 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.
- Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. In Michele Flammini, Enrico Nardelli, Guido Proietti, and Paul 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.
- 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. An updated version appears in Journal of Algorithms, and an extended abstract appears in SODA '01.
- 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. Extended abstract published in SIROCCO '00, and an updated version is available in Journal of Discrete Algorithms.
- 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.
- 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.
- 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.
- Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245(2):217-253, 2000. Updated version of RR-1182-97 (1997).A HTML version available here.
- Cyril Gavoille. On the dilation of interval routing. The Computer Journal, 43(1):1-7, 2000. Updated version of RR-1145-96 (1996).
1999
- Cyril Gavoille and David Peleg. The compactness of interval routing. SIAM Journal on Discrete Mathematics, 12(4):459-473, October 1999. Updated version of RR-1176-97 (1997).
- Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Jirí 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.
- 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.
- 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).
- Cyril Gavoille and Nicolas Hanusse. Routage compact dans les réseaux de genre borné. In 1ère Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1-5. INRIA, May 1999. Apparaît aussi dans RR-1213-99 (1999).
- Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. Research Report RR-1213-99, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 1999. Extended abstract published in ICALP '99, and a revised version is available here.
1998
- Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. In Shay Kutten, editor, 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).
- Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. In 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, August 1998. An updated version appears in Journal of Algorithms. Appears also as RR-1195-98 (1998). Slides available here.
- Pierre Fraigniaud and Cyril Gavoille. A theoretical model for routing complexity. In Luisa Gargano and David Peleg, editors, 5th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 98-113. Carleton Scientific, July 1998.
- 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. Extended abstract published in DISC '98, and a revised version appears in SIAM J. on Computing.
- Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Algorithmica, 21:155-182, 1998. Updated version of RR94-04 (1994).
- Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Research Report RR-1195-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, January 1998. A part appears in Journal of Algorithms (and an extended abstract has been published in PODC '98), and another part appears here.
- 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).
1997
- Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Research Report RR-1181-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. Extended abstract published in SIROCCO '97. Appears also in JPDC.
- Cyril Gavoille. A survey on interval routing scheme. Research Report RR-1182-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. An updated version appears in TCS, and a HTML version available here.
- Cyril Gavoille and David Peleg. The compactness of interval routing. Research Report RR-1176-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 1997. An updated version appears in SIAM Journal on Discrete Mathematics.
- Cyril Gavoille. On the dilation of interval routing. In Igor Prívara 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).
- 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).
- Cyril Gavoille. Compact routing: Lower bounds techniques (invited lecture). In International Research School on "Sense of Direction and Compact Routing", June 1997.
- Pierre Fraigniaud and Cyril Gavoille. Universal routing schemes. Distributed Computing, 10:65-78, 1997. Updated version of RR95-05 (1995).
1996
- Cyril Gavoille. On dilation of interval routing. Research Report RR-1145-96, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 1996. An updated version appears in The Computer Journal and in MFCS '97.
- Cyril Gavoille. Lower bounds for interval routing on bounded degree networks. Research Report RR-1144-96, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1996. Submitted for publication.
- 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 Journal of Distributed Computing (1997).
- Cyril Gavoille and Stéphane Pérennès. Lower bounds for interval routing on 3-regular networks. In Nicola Santoro and Paul Spirakis, editors, 3rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 88-103. Carleton University Press, June 1996.
- 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).
- 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.
- Cyril Gavoille. Complexité mémoire du routage dans les réseaux distribués. PhD thesis, École Normale Supérieure de Lyon, 46, allée d'Italie, January 1996. The cover page is available here.
- Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. Research Report 96-01, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1996. Extended abstract published in SPAA '96.
1995
- Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. Research Report 95-46, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, December 1995. Extended abstract published in PODC '96.
- 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 the Journal of Distributed Computing.
- 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.
- Cyril Gavoille and Eric Guévremont. On the compactness of bounded degree graphs for shortest path interval routing. In 2nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 113-121. Carleton University Press, June 1995.
- Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. Research Report 95-05, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, March 1995. An updated version is available in the Journal of Distributed Computing.
- Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Research Report 95-02, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1995. An updated version appears in Journal of Algorithms.
1994
- Pierre Fraigniaud and Cyril Gavoille. Optimal interval routing. In Bruno Buchberger and Jens Volkert, editors, Parallel Processing: CONPAR '94 - VAPP VI, volume 854 of Lecture Notes in Computer Science, pages 785-796. Springer-Verlag, September 1994.
- Pierre Fraigniaud and Cyril Gavoille. A characterization of networks supporting linear interval routing. In 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 216-224. ACM Press, August 1994.
- Cyril Gavoille. Routages efficaces et compacts. In Luc Bougé, Michel Cosnard, and Pierre Fraigniaud, editors, 6èmes Rencontres Francophones du Parallélisme (RenPar), page 298, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1994.
- Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Research Report 94-04, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1994. An updated version appears in Algorithmica.
1993
- 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).
- Cyril Gavoille. Routage par intervalles. Stage de DEA, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1993.
- 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
- 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.
10 janvier 2008 (168)
[home page of the team]