%------ 2007 --------------------------------------------------------- @INPROCEEDINGS{GL07b, AUTHOR = {Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Distributed Relationship Schemes for Trees}, BOOKTITLE = {$18^{th}$ Annual International Symposium on Algorithms and Computation (ISAAC)}, PUBLISHER = {Springer}, VOLUME = {4835 of Lecture Notes in Computer Science}, LOCATION = {Sendai, Japan}, PAGES = {728-738}, MONTH = dec, YEAR = 2007, KEYWORDS = {labeling scheme, tree}, DOI = {10.1007/978-3-540-77120-3_63} } @TECHREPORT{GKKKN07b, AUTHOR = {Gavoille, Cyril and Klasing, Ralf and Kosowski, Adrian and Kuszner, {\L}ukasz and Navarra, Alfredo}, TITLE = {On the Complexity of Distributed Graph Coloring with Local Minimality Constraints}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1440-07}, MONTH = dec, YEAR = 2007, KEYWORDS = {coloring, distributed, decomposition} } @TECHREPORT{GKKKN07, AUTHOR = {Gavoille, Cyril and Klasing, Ralf and Kosowski, Adrian and Kuszner, {\L}ukasz and Navarra, Alfredo}, TITLE = {On the Complexity of Distributed Graph Coloring with Local Minimality Constraints}, INSTITUTION= {INRIA}, TYPE = {{Research Report}}, NUMBER = {6399}, MONTH = dec, YEAR = 2007, KEYWORDS = {coloring, distributed, decomposition} } @INPROCEEDINGS{GL07c, AUTHOR = {Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Sch\'ema relationnel distribu\'e pour les arbres}, BOOKTITLE = {$9^{\mbox{\`emes}}$ Journ\'ees Graphes et Algorithmes}, LOCATION = {Insititut Henri Poincar\'e, Paris}, PAGES = 19, MONTH = nov, YEAR = 2007, KEYWORDS = {labeling scheme, tree} } @INPROCEEDINGS{GL07, AUTHOR = {Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs}, BOOKTITLE = {$15^{th}$ Annual European Symposium on Algorithms (ESA)}, PUBLISHER = {Springer}, EDITOR = {Lars Arge and Emo Welzl}, VOLUME = {4698 of Lecture Notes in Computer Science}, LOCATION = {Eilat, Israel}, PAGES = {582-593}, MONTH = oct, YEAR = 2007, KEYWORDS = {distance labeling, planar, tree-decomposition} } @INPROCEEDINGS{DGP07, AUTHOR = {Derbel, Bilel and Gavoille, Cyril and Peleg, David}, TITLE = {Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time}, BOOKTITLE = {$21^{st}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, VOLUME = {4731 of Lecture Notes in Computer Science}, PAGES = {179-192}, MONTH = sep, YEAR = 2007, KEYWORDS = {spanner, distributed} } @ARTICLE{DDGY07, AUTHOR = {Dourisboure, Yon and Dragan, Feodor F. and Gavoille, Cyril and Yan, Chenyu}, TITLE = {Spanners for Bounded Tree-Length Graphs}, JOURNAL = {Theoretical Computer Science}, VOLUME = 383, NUMBER = 1, PAGES = {34-44}, MONTH = sep, YEAR = 2007, KEYWORDS = {spanner, tree-decomposition}, DOI = {10.1016/j.tcs.2007.03.058} } @INPROCEEDINGS{GKKN07, AUTHOR = {Gavoille, Cyril and Klasing, Ralf and Kosowski, Adrian and Navarra, Alfredo}, TITLE = {Brief Announcement: On the Complexity of Distributed Greedy Coloring}, BOOKTITLE = {$21^{st}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, VOLUME = {4731 of Lecture Notes in Computer Science}, PAGES = {482-484}, MONTH = sep, YEAR = 2007, KEYWORDS = {coloring, distributed} } @INPROCEEDINGS{CGKT07, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mustapha and Twigg, David Andrew}, TITLE = {Forbidden-Set Labeling on Graphs}, BOOKTITLE = {$2^{nd}$ Workshop on Locality Preserving Distributed Computing Methods (LOCALITY)}, NOTE = {Co-located with PODC 2007}, LOCATION = {Portland, Oregon, USA}, MONTH = aug, YEAR = 2007, KEYWORDS = {labeling scheme, planar, forbidden} } @INPROCEEDINGS{GL07a, AUTHOR = {Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Brief Annoucement: On Local Representation of Distances in Trees}, BOOKTITLE = {$26^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, LOCATION = {Portland, WA, USA}, PAGES = {246-247}, MONTH = aug, YEAR = 2007, KEYWORDS = {distance labeling}, DOI = {10.1145/1281100.1281169} } @INPROCEEDINGS{i:Gav07a, AUTHOR = {Gavoille, Cyril}, TITLE = {Localized Data Structures (Keynote Talk)}, BOOKTITLE = {$2^{nd}$ Workshop on Locality Preserving Distributed Computing Methods (LOCALITY)}, NOTE = {Co-located with PODC 2007}, LOCATION = {Portland, Oregon, USA}, MONTH = aug, YEAR = 2007, KEYWORDS = {labeling scheme, data-structure} } @INPROCEEDINGS{FGIP07, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Ilcinkas, David and Pelc, Andrzej}, TITLE = {Distributed Computing with Advice: Information Sensitivity of Graph Coloring}, BOOKTITLE = {$34^{th}$ International Colloquium on Automata, Languages and Programming (ICALP)}, PUBLISHER = {Springer}, VOLUME = {4596 of Lecture Notes in Computer Science}, PAGES = {231-242}, MONTH = jul, YEAR = 2007, KEYWORDS = {coloring, distributed}, DOI = {10.1007/978-3-540-73420-8_22} } @INPROCEEDINGS{FGKLL07, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Kosowski, Adrian and Lebhar, Emmanuelle and Lotker, Zvi}, TITLE = {Universal Augmentation Schemes for Network Navigability: Overcoming the $\sqrt{n}$-Barrier}, BOOKTITLE = {$19^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {San Diego, CA, USA}, PAGES = {1-7}, MONTH = jun, YEAR = 2007, KEYWORDS = {small world, tree-decomposition} } @INPROCEEDINGS{AGMW07, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Wieder, Udi}, TITLE = {Strong-Diameter Decompositions of Minor Free Graphs}, BOOKTITLE = {$19^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {San Diego, CA, USA}, PAGES = {16-24}, MONTH = jun, YEAR = 2007, KEYWORDS = {decomposition, planar, minor, compact routing} } @INPROCEEDINGS{FGKLL07a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Kosowski, Adrian and Lebhar, Emmanuelle and Lotker, Zvi}, TITLE = {A propos des sch\'emas d'augmentation universels pour la navigation dans les r\'eseaux}, BOOKTITLE = {$9^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PAGES = {23-26}, MONTH = may, YEAR = 2007, KEYWORDS = {small world, tree-decomposition} } @INPROCEEDINGS{DG07a, AUTHOR = {Dieng, Youssou and Gavoille, Cyril}, TITLE = {Routage dans les graphes cellulaires}, BOOKTITLE = {$9^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PAGES = {91-94}, MONTH = may, YEAR = 2007, KEYWORDS = {compact routing, outerplanar} } @INPROCEEDINGS{i:Gav07, AUTHOR = {Gavoille, Cyril}, TITLE = {An Overview on Compact Routing}, BOOKTITLE = {Workshop on Peer-to-Peer, Routing in Complex Graphs, and Network Coding}, LOCATION = {Thomson Labs - Paris}, MONTH = mar, YEAR = 2007, KEYWORDS = {compact routing} } @ARTICLE{EGP07, AUTHOR = {Eilam, Tamar and Gavoille, Cyril and Peleg, David}, TITLE = {Average Stretch Analysis of Compact Routing Schemes}, JOURNAL = {Discrete Applied Mathematics}, VOLUME = 155, PAGES = {598-610}, MONTH = jan, YEAR = 2007, KEYWORDS = {compact routing, interval routing}, DOI = {10.1016/j.dam.2006.09.010} } @ARTICLE{DG07b, AUTHOR = {Derbel, Bilel and Gavoille, Cyril}, TITLE = {Fast Deterministic Distributed Algorithms for Sparse Spanners}, JOURNAL = {Theoretical Computer Science}, NOTE = {To appear}, YEAR = 2007, KEYWORDS = {spanner, distributed} } @ARTICLE{DG07, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Tree-Decompositions with Bags of Small Diameter}, JOURNAL = {Discrete Mathematics}, VOLUME = 307, NUMBER = 16, PAGES = {2008-2029}, YEAR = 2007, KEYWORDS = {spanner, tree-decomposition}, DOI = {10.1016/j.disc.2005.12.060} } @ARTICLE{BG07, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Localized and Compact Data-Structure for Comparability Graphs}, JOURNAL = {Discrete Mathematics}, YEAR = 2007, NOTE = {to appear}, KEYWORDS = {data-structure, permutation graph, labeling scheme}, DOI = {10.1016/j.disc.2007.12.091} } @ARTICLE{GP07, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Optimal distance labeling for interval graphs and related graphs families}, JOURNAL = {SIAM Journal on Discrete Mathematics}, NOTE = {To appear}, YEAR = 2007, KEYWORDS = {distance labeling, circular-arc, interval graph} } %------ 2006 --------------------------------------------------------- @TECHREPORT{AGMW06, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Wieder, Udi}, TITLE = {Strongly-Bounded Sparse Decompositions of Minor Free Graphs}, INSTITUTION= {Microsoft Research}, ADDRESS = {Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com}, NUMBER = {MSR-TR-2006-192}, MONTH = dec, YEAR = 2006, KEYWORDS = {decomposition, compact routing, minor} } @INPROCEEDINGS{BGL06c, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Sch\'ema d'\'etiquetage d'adjacence pour les arbres de degr\'es born\'e}, BOOKTITLE = {$8^{\mbox{\`emes}}$ Journ\'ees Graphes et Algorithmes}, LOCATION = {Orl\'eans}, MONTH = nov, YEAR = 2006, KEYWORDS = {labeling scheme, universal graph} } @INPROCEEDINGS{i:Gav06a, AUTHOR = {Gavoille, Cyril}, TITLE = {An Overview on Compact Routing}, BOOKTITLE = {$2^{nd}$ Research Workshop on Flexible Network Design}, LOCATION = {University of Bologna Residential Center Bertinoro (Forl\`\i), Italy}, MONTH = oct, YEAR = 2006, KEYWORDS = {compact routing} } @INPROCEEDINGS{i:Gav06, AUTHOR = {Gavoille, Cyril}, TITLE = {Distributed Data Structures: A Survey on Informative Labeling Schemes (Invited Talk)}, BOOKTITLE = {$31^{st}$ International Symposium on Mathematical Foundations of Computer Science (MFCS)}, EDITOR = {R. Kr\'alovic and P. Urzyczyn}, PUBLISHER = {Springer}, VOLUME = {4162 of Lecture Notes in Computer Science}, LOCATION = {High Tatras, Slovakia}, PAGES = 38, MONTH = aug, YEAR = 2006, KEYWORDS = {labeling scheme, data-structure} } @ARTICLE{FG06, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Header-Size Lower Bounds for End-to-End Communication in Memoryless Networks}, JOURNAL = {Computer Networks}, VOLUME = 50, NUMBER = 10, PAGES = {1630-1638}, MONTH = jul, YEAR = 2006, KEYWORDS = {end-to-end} } @INPROCEEDINGS{DG06, AUTHOR = {Derbel, Bilel and Gavoille, Cyril}, TITLE = {Fast Deterministic Distributed Algorithms for Sparse Spanners}, BOOKTITLE = {$13^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Springer}, VOLUME = {4056 of Lecture Notes in Computer Science}, PAGES = {100-114}, MONTH = jul, YEAR = 2006, KEYWORDS = {spanner, distributed}, DOI = {10.1007/11780823_9} } @INPROCEEDINGS{BGL06b, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Adjacency labeling for bounded degree trees and applications}, BOOKTITLE = {$6^{th}$ Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications}, LOCATION = {Prague}, MONTH = jul, YEAR = 2006, NOTE = {Dedicated to Jarik Ne\v{s}et\v{r}il on the occasion of his 60th birthday}, KEYWORDS = {labeling scheme} } @INPROCEEDINGS{BGL06, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Short Labels by Traversal and Jumping}, BOOKTITLE = {$13^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Springer}, VOLUME = {4056 of Lecture Notes in Computer Science}, PAGES = {143-156}, MONTH = jul, YEAR = 2006, KEYWORDS = {tree, labeling scheme}, DOI = {10.1007/11780823_12} } @INPROCEEDINGS{AGGM06, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Goldberg, Andrew V. and Malkhi, Dahlia}, TITLE = {Routing in Networks with Low Doubling Dimension}, BOOKTITLE = {$26^{th}$ International Conference on Distributed Computing Systems (ICDCS)}, PUBLISHER = {IEEE Computer Society Press}, LOCATION = {Lisboa, Portugal}, MONTH = jul, YEAR = 2006, KEYWORDS = {compact routing, doubling dimension} } @INPROCEEDINGS{AGM06b, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {On Space-Stretch Trade-Offs: Lower Bounds}, BOOKTITLE = {$18^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {Cambridge, Massachusetts, USA}, PAGES = {217-224}, MONTH = jul, YEAR = 2006, KEYWORDS = {compact routing, name-independent}, DOI = {10.1145/1148109.1148143} } @INPROCEEDINGS{AGM06a, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {On Space-Stretch Trade-Offs: Upper Bounds}, BOOKTITLE = {$18^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {Cambridge, Massachusetts, USA}, PAGES = {207-216}, MONTH = jul, YEAR = 2006, KEYWORDS = {compact routing, name-independent}, DOI = {10.1145/1148109.1148144} } @INPROCEEDINGS{AG06, AUTHOR = {Abraham, Ittai and Gavoille, Cyril}, TITLE = {Object Location Using Path Separators}, BOOKTITLE = {$25^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, LOCATION = {Denver, Colorado, USA}, PAGES = {188-197}, MONTH = jul, YEAR = 2006, KEYWORDS = {minor, small world, compact routing, labeling scheme} } @ARTICLE{FGP06, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Paul, Christophe}, TITLE = {Eclecticism Shrinks Even Small Worlds}, JOURNAL = {Distributed Computing}, PUBLISHER = {Springer-Verlag}, VOLUME = 18, NUMBER = 4, PAGES = {279-291}, MONTH = mar, YEAR = 2006, DOI = {10.1007/s00446-005-0137-4}, KEYWORDS = {small world} } @TECHREPORT{BGL06a, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Short Labels by Traversal and Jumping}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1389-06}, MONTH = mar, YEAR = 2006, KEYWORDS = {tree, labeling scheme} } @TECHREPORT{AG06a, AUTHOR = {Abraham, Ittai and Gavoille, Cyril}, TITLE = {Object Location Using Path Separators}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1394-06}, MONTH = mar, YEAR = 2006, KEYWORDS = {minor, small world, compact routing, labeling scheme} } @TECHREPORT{DG06a, AUTHOR = {Derbel, Bilel and Gavoille, Cyril}, TITLE = {Fast Deterministic Distributed Algorithms for Sparse Spanners}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1388-06}, MONTH = feb, YEAR = 2006, KEYWORDS = {spanner, distributed} } @ARTICLE{BGHPS06, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Poulalhon, Dominique and Schaeffer, Gilles}, TITLE = {Planar Graphs, via Well-Orderly Maps and Trees}, JOURNAL = {Graphs and Combinatorics}, VOLUME = 22, NUMBER = 2, PAGES = {185-202}, YEAR = 2006, KEYWORDS = {coding, planar}, DOI = {10.1007/s00373-006-0647-2} } %------ 2005 --------------------------------------------------------- @INPROCEEDINGS{BG05b, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Localized and Compact Data-Structure for Comparability Graphs}, BOOKTITLE = {$16^{th}$ Annual International Symposium on Algorithms and Computation (ISAAC)}, PUBLISHER = {Springer}, VOLUME = {3827 of Lecture Notes in Computer Science}, LOCATION = {Sanya, Hainan, China}, PAGES = {1122-1131}, MONTH = dec, YEAR = 2005, DOI = {10.1007/11602613_111}, KEYWORDS = {data-structure, permutation graph, labeling scheme} } @TECHREPORT{AGGM05, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Goldberg, Andrew V. and Malkhi, Dahlia}, TITLE = {Routing in Networks with Low Doubling Dimension}, INSTITUTION= {Microsoft Research}, ADDRESS = {Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com}, NUMBER = {MSR-TR-2005-175}, MONTH = dec, YEAR = 2005, KEYWORDS = {compact routing, doubling dimension} } @INPROCEEDINGS{GL05, AUTHOR = {Gavoille, Cyril and Ly, Olivier}, TITLE = {Distance Labeling in Hyperbolic Graphs}, BOOKTITLE = {$16^{th}$ Annual International Symposium on Algorithms and Computation (ISAAC)}, PUBLISHER = {Springer}, VOLUME = {3827 of Lecture Notes in Computer Science}, LOCATION = {Sanya, Hainan, China}, PAGES = {1071-1079}, MONTH = dec, YEAR = 2005, DOI = {10.1007/11602613_106}, KEYWORDS = {distance labeling, hyperbolic} } @TECHREPORT{AGM05a, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {On Space-Stretch Trade-Offs for Compact Routing Schemes}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1374-05}, MONTH = nov, YEAR = 2005, KEYWORDS = {compact routing, name-independent} } @INPROCEEDINGS{BGL05, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Edge Partition of Toroidal Graphs into Forests in Linear Time}, BOOKTITLE = {$7^{th}$ International Conference on Graph Theory (ICGT)}, LOCATION = {Hy\`eres, France}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 22, MONTH = oct, PAGES = {421-425}, YEAR = 2005, KEYWORDS = {torus, decomposition}, DOI = {10.1016/j.endm.2005.06.065} } @INPROCEEDINGS{BG05a, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Distance Labeling for Permutation Graphs}, BOOKTITLE = {$7^{th}$ International Conference on Graph Theory (ICGT)}, LOCATION = {Hy\`eres, France}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 22, MONTH = oct, PAGES = {461-467}, YEAR = 2005, KEYWORDS = {permutation graph, labeling scheme}, DOI = {10.1016/j.endm.2005.06.098} } @INPROCEEDINGS{AGM05, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {Compact Routing for Graphs Excluding a Fixed Minor}, BOOKTITLE = {$19^{th}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, VOLUME = {3724 of Lecture Notes in Computer Science}, PAGES = {442-456}, MONTH = sep, YEAR = 2005, DOI = {10.1007/11561927_32}, KEYWORDS = {compact routing, name-independent, minor} } @INPROCEEDINGS{i:Gav05b, AUTHOR = {Gavoille, Cyril}, TITLE = {Distributed Data Structures: A Survey {I} \& {II}}, BOOKTITLE = {$8^{th}$ Seminar on Optimization and Decision Aid (SODA), France Télécom R\&{}D Division}, LOCATION = {Sophia-Antipolis, France}, MONTH = jun, YEAR = 2005, KEYWORDS = {labeling scheme, data-structure} } @INPROCEEDINGS{i:Gav05, AUTHOR = {Gavoille, Cyril}, TITLE = {Distributed Data Structures: A Survey (Invited Talk)}, BOOKTITLE = {$12^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Springer}, VOLUME = {3499 of Lecture Notes in Computer Science}, LOCATION = {Mont St-Michel, France}, MONTH = may, PAGES = 2, YEAR = 2005, KEYWORDS = {labeling scheme, data-structure} } @INPROCEEDINGS{i:Gav05c, AUTHOR = {Gavoille, Cyril}, TITLE = {{\'E}tiquetage des graphes}, BOOKTITLE = {{\'E}cole Jeunes Chercheurs en Algorithmique et Calcul Formel - \'Ecole thématique CNRS 05 13 051}, LOCATION = {Montpellier}, MONTH = apr, YEAR = 2005, KEYWORDS = {labeling scheme} } @TECHREPORT{BG05, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Localized and Compact Data-Structure for Comparability Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1343-05}, MONTH = feb, YEAR = 2005, KEYWORDS = {data-structure, permutation graph, labeling scheme} } @ARTICLE{BGH05, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation}, JOURNAL = {Journal of Graph Algorithms and Applications}, VOLUME = 9, NUMBER = 2, PAGES = {185-204}, YEAR = 2005, KEYWORDS = {counting, coding, outerplanar} } @ARTICLE{GN05, AUTHOR = {Gavoille, Cyril and Neh\'ez, Martin}, TITLE = {Interval Routing in Reliability Networks}, JOURNAL = {Theoretical Computer Science}, YEAR = 2005, VOLUME = 333, NUMBER = 3, PAGES = {415-432}, KEYWORDS = {interval routing, percolation} } @ARTICLE{GH05, AUTHOR = {Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {On Compact Encoding of Pagenumber $k$ Graphs}, JOURNAL = {Discrete Mathematics \& Theoretical Computer Science}, NOTE = {To appear}, YEAR = 2005, KEYWORDS = {data-structure} } %------ 2004 --------------------------------------------------------- @INPROCEEDINGS{FDGM04, AUTHOR = {Ferchaud, Fr\'{e}d\'{e}ric and Duong, Vu and Gavoille, Cyril and Mosbah, Mohamed}, TITLE = {Reducing Disturbances by Using Absorption Areas}, BOOKTITLE = {$1^{st}$ International Conference on Research in Air Transportation (ICRAT)}, LOCATION = {Zilina, Slovac Republik}, ISBN = {80-8070-196-2}, PAGES = {111-115}, MONTH = nov, YEAR = 2004, KEYWORDS = {atfm} } @INPROCEEDINGS{AGM04, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {Routing with Improved Communication-Space Trade-Off}, BOOKTITLE = {$18^{th}$ International Symposium on Distributed Computing (DISC)}, LOCATION = {Amsterdam, The Netherlands}, PUBLISHER = {Springer}, VOLUME = {3274 of Lecture Notes in Computer Science}, PAGES = {305-319}, MONTH = oct, YEAR = 2004, KEYWORDS = {compact routing, name-independent} } @INPROCEEDINGS{DFGM04a, AUTHOR = {Duong, Vu and Ferchaud, Fr\'{e}d\'{e}ric and Gavoille, Cyril and Mosbah, Mohamed}, TITLE = {Using Absorption Areas to Improve {ATFM}}, BOOKTITLE = {$23^{rd}$ IEEE International Digital Avionics Systems Conference (DASC)}, LOCATION = {Salt Lake City, USA}, ISBN = {0-7803-8539-X}, MONTH = oct, YEAR = 2004, KEYWORDS = {atfm} } @INPROCEEDINGS{DFGM04, AUTHOR = {Duong, Vu and Ferchaud, Fr\'{e}d\'{e}ric and Gavoille, Cyril and Mosbah, Mohamed}, TITLE = {A New Slot Allocation for {ATFM}}, BOOKTITLE = {$7^{th}$ IEEE International Conference on Intelligent Transportation Systems (ITSC)}, LOCATION = {Washington, D.C.}, ISBN = {0-7803-8501-2}, PAGES = {1075-1079}, MONTH = oct, YEAR = 2004, KEYWORDS = {atfm} } @INPROCEEDINGS{BG04, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Etiquetage de Distance des Graphes de Permutation}, BOOKTITLE = {$6^{\mbox{\`emes}}$ Journées Graphes et Algorithmes}, LOCATION = {Grenoble}, EDITOR = {E. Duch\`ene et S. Gravier}, PUBLISHER = {Les Cahiers du laboratoire Leibniz, No~114}, PAGES = {22-24}, MONTH = oct, YEAR = 2004, KEYWORDS = {permutation graph, labeling scheme} } @TECHREPORT{BGHPS04a, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Poulalhon, Dominique and Schaeffer, Gilles}, TITLE = {Planar Graphs, via Well-Orderly Maps and Trees}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, MONTH = sep, YEAR = 2004, KEYWORDS = {coding, planar} } @INPROCEEDINGS{FGP04, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Paul, Christophe}, TITLE = {Eclecticism Shrinks Even Small Worlds}, BOOKTITLE = {$23^{rd}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, LOCATION = {St. John's, Newfoundland, Canada}, PUBLISHER = {ACM Press}, PAGES = {169-178}, MONTH = jul, YEAR = 2004, KEYWORDS = {small world} } @TECHREPORT{AGM04a, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia}, TITLE = {Routing with Improved Communication-Space Trade-Off}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1330-04}, MONTH = jul, YEAR = 2004, KEYWORDS = {compact routing, name-independent} } @INPROCEEDINGS{AGMNT04, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Nisan, Noam and Thorup, Mikkel}, TITLE = {Compact Name-Independent Routing with Minimum Stretch}, BOOKTITLE = {$16^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, PAGES = {20-24}, MONTH = jul, YEAR = 2004, KEYWORDS = {compact routing, name-independent} } @INPROCEEDINGS{DG04, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Sparse Additive Spanners for Bounded Tree-Length Graphs}, BOOKTITLE = {$11^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Springer}, VOLUME = {3104 of Lecture Notes in Computer Science}, PAGES = {123-137}, MONTH = jun, YEAR = 2004, ISBN = {3-540-22230-8}, DOI = {10.1007/b98251}, KEYWORDS = {spanner} } @INPROCEEDINGS{BGHPS04, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Poulalhon, Dominique and Schaeffer, Gilles}, TITLE = {Planar Graphs, via Well-Orderly Maps and Trees}, BOOKTITLE = {$30^{th}$ International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, PUBLISHER = {Springer}, VOLUME = {3353 of Lecture Notes in Computer Science}, NOTE = {270-284}, MONTH = jun, YEAR = 2004, DOI = {10.1007/b104584}, KEYWORDS = {coding, planar} } @INPROCEEDINGS{FGP04a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Paul, Christophe}, TITLE = {Eclectisme dans les petits mondes}, BOOKTITLE = {$6^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, MONTH = may, YEAR = 2004, KEYWORDS = {small world} } @TECHREPORT{DG04b, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Small Diameter Bag Tree-Decompositions}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1326-04}, MONTH = may, YEAR = 2004, KEYWORDS = {spanner, tree-decomposition} } @TECHREPORT{DG04a, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Sparse Additive Spanners for Bounded Tree-Length Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1316-04}, MONTH = feb, YEAR = 2004, KEYWORDS = {spanner, tree-decomposition} } @ARTICLE{AGKR04, AUTHOR = {Alstrup, Stephen and Gavoille, Cyril and Kaplan, Haim and Rauhe, Theis}, TITLE = {Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment}, JOURNAL = {Theory of Computing Systems}, VOLUME = 37, PAGES = {441-456}, YEAR = 2004, KEYWORDS = {labeling scheme, nca}, DOI = {10.1007/s00224-004-1155-5} } @TECHREPORT{CGMF04, AUTHOR = {Castanet, Richard and Gavoille, Cyril and Mosbah, Mohamed and Ferchaud, Fr\'ed\'eric}, TITLE = {Utilisation des zones d'absorption pour améliorer la gestion de flux du trafic aérien}, INSTITUTION= {LaBRI, Universit\'e Bordeaux~1 - ENSEIRB}, TYPE = {Rapport de contrat (intermédiaire)}, NUMBER = {march\'e C/1.291/CE/NB/03/}, MONTH = jan, YEAR = 2004, KEYWORDS = {contract} } @ARTICLE{GPPR04, AUTHOR = {Gavoille, Cyril and Peleg, David and P\'{e}renn\`{e}s, St\'{e}phane and Raz, Ran}, TITLE = {Distance Labeling in Graphs}, JOURNAL = {Journal of Algorithms}, VOLUME = 53, NUMBER = 1, PAGES = {85-112}, YEAR = 2004, DOI = {10.1016/j.jalgor.2004.05.002}, KEYWORDS = {distance labeling} } %------ 2003 --------------------------------------------------------- @INPROCEEDINGS{FGM03, AUTHOR = {Ferchaud, Fr\'{e}d\'{e}ric and Gavoille, Cyril and Mosbah, Mohamed}, TITLE = {Using Absorption Areas to Improve {ATFM}}, BOOKTITLE = {ERC Innovative Research Workshop}, MONTH = dec, YEAR = 2003, KEYWORDS = {atfm} } @MISC{CGMF03, AUTHOR = {Castanet, Richard and Gavoille, Cyril and Mosbah, Mohamed and Ferchaud, Fr\'ed\'eric}, TITLE = {Gestion de flux du traffic aérien en intra et inter réseaux~: un modèle de graphes évolutifs}, INSTITUTION= {LaBRI, Universit\'e Bordeaux~1 - ENSEIRB}, TYPE = {Rapport de contrat (final)}, NUMBER = {march\'e C20135E/DM/02 - EUROCONTROL}, MONTH = nov, YEAR = 2003, KEYWORDS = {contract} } @TECHREPORT{FGP03, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Paul, Christophe}, TITLE = {Eclecticism Shrinks the World}, INSTITUTION= {LRI}, ADDRESS = {Universit\'{e} Paris-Sud, 91405 Orsay cedex, France}, TYPE = {{Research Report}}, NUMBER = {LRI-1376}, MONTH = oct, YEAR = 2003, KEYWORDS = {small world} } @INPROCEEDINGS{FG03, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Lower Bounds for Oblivious Single-Packet End-to-End Communication}, BOOKTITLE = {$17^{th}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, VOLUME = {2848 of Lecture Notes in Computer Science}, PAGES = {211-223}, MONTH = oct, YEAR = 2003, KEYWORDS = {end-to-end} } @INPROCEEDINGS{DG03, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Tree-Decomposition of Graphs with small Diameter Bags}, BOOKTITLE = {$2^{nd}$ European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB)}, EDITOR = {Fila, J.}, ISBN = {80-239-1185-6}, PAGES = {100-104}, MONTH = sep, YEAR = 2003, KEYWORDS = {spanner, tree-decomposition} } @INPROCEEDINGS{GP03, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Optimal Distance Labeling Schemes for Interval and Circular-arc Graphs}, BOOKTITLE = {$11^{th}$ Annual European Symposium on Algorithms (ESA)}, EDITOR = {G. Di Battista and U. Zwick}, PUBLISHER = {Springer}, VOLUME = {2832 of Lecture Notes in Computer Science}, PAGES = {254-265}, MONTH = sep, YEAR = 2003, KEYWORDS = {distance labeling, circular-arc, interval graph}, DOI = {10.1007/b13632} } @INPROCEEDINGS{GN03b, AUTHOR = {Gavoille, Cyril and Neh\'ez, Martin}, TITLE = {On Interval Routing in Random Meshes}, BOOKTITLE = {$2^{nd}$ European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB)}, EDITOR = {Fila, J.}, ISBN = {80-239-1185-6}, PAGES = {147-150}, MONTH = sep, YEAR = 2003, KEYWORDS = {interval routing, percolation} } @INPROCEEDINGS{BGH03c, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation}, BOOKTITLE = {$29^{th}$ International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, PUBLISHER = {Springer-Verlag}, VOLUME = {2880 of Lecture Notes in Computer Science}, PAGES = {81-92}, MONTH = jun, YEAR = 2003, KEYWORDS = {counting, coding, outerplanar}, DOI = {10.1007/b93953} } @INPROCEEDINGS{GN03, AUTHOR = {Gavoille, Cyril and Neh\'ez, Martin}, TITLE = {Interval Routing in Reliability Networks}, BOOKTITLE = {$9^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Carleton University Press}, PAGES = {149-164}, MONTH = jun, YEAR = 2003, KEYWORDS = {interval routing, percolation} } @ARTICLE{GP03c, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {Compact and Localized Distributed Data Structures}, JOURNAL = {Distributed Computing}, PUBLISHER = {Springer-Verlag}, VOLUME = 16, PAGES = {111-120}, MONTH = may, YEAR = 2003, NOTE = {PODC 20-Year Special Issue}, KEYWORDS = {labeling scheme, data-structure} } @TECHREPORT{BGH03b, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1295-03}, MONTH = mar, YEAR = 2003, KEYWORDS = {counting, coding, outerplanar} } @TECHREPORT{GN03a, AUTHOR = {Gavoille, Cyril and Neh\'ez, Martin}, TITLE = {Interval Routing in Reliability Networks}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1294-03}, MONTH = mar, YEAR = 2003, KEYWORDS = {interval routing, percolation} } @TECHREPORT{FG03a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Lower Bounds for Oblivious Single-Message End-to-End Communication}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1289-03}, MONTH = feb, YEAR = 2003, KEYWORDS = {end-to-end} } @INPROCEEDINGS{BGH03, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation}, BOOKTITLE = {$20^{th}$ Annual Symposium on Theoretical Aspects of Computer Science (STACS)}, PUBLISHER = {Springer}, VOLUME = {2607 of Lecture Notes in Computer Science}, PAGES = {499-510}, MONTH = feb, YEAR = 2003, KEYWORDS = {planar, counting, coding} } @TECHREPORT{GP03a, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Small Universal Distance Matrices}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1290-03}, MONTH = feb, YEAR = 2003, KEYWORDS = {distance labeling, circular-arc, interval graph} } @ARTICLE{EGP03, AUTHOR = {Eilam, Tamar and Gavoille, Cyril and Peleg, David}, TITLE = {Compact Routing Schemes With Low Stretch Factor}, JOURNAL = {Journal of Algorithms}, VOLUME = 46, NUMBER = 2, PAGES = {97-114}, YEAR = 2003, KEYWORDS = {compact routing, interval routing} } @ARTICLE{GZ03, AUTHOR = {Gavoille, Cyril and Zemmari, Akka}, TITLE = {The Compactness of Adaptive Routing Tables}, JOURNAL = {Journal of Discrete Algorithms}, VOLUME = 1, NUMBER = 2, PAGES = {237-254}, YEAR = 2003, KEYWORDS = {interval routing} } @ARTICLE{GP03b, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Distance Labeling Scheme and Split Decomposition}, JOURNAL = {Discrete Mathematics}, VOLUME = 273, NUMBER = {1-3}, PAGES = {115-130}, YEAR = 2003, KEYWORDS = {distance labeling} } %------ 2002 --------------------------------------------------------- @INPROCEEDINGS{DG02, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Improved Compact Routing Scheme for Chordal Graphs}, BOOKTITLE = {$16^{th}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, PAGES = {252-264}, VOLUME = {2508 of Lecture Notes in Computer Science}, MONTH = oct, YEAR = 2002, KEYWORDS = {compact routing, chordal} } @TECHREPORT{BGH02, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {An Information Upper Bound of Planar Graphs Using Triangulation}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1279-02}, MONTH = sep, YEAR = 2002, KEYWORDS = {planar, counting, coding} } @INPROCEEDINGS{AGKR02, AUTHOR = {Alstrup, Stephen and Gavoille, Cyril and Kaplan, Haim and Rauhe, Theis}, TITLE = {Nearest Common Ancestors: A Survey and a new Distributed Algorithm}, BOOKTITLE = {$14^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, PAGES = {258-264}, MONTH = aug, YEAR = 2002, KEYWORDS = {labeling scheme, nca} } @TECHREPORT{DG02a, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Improved Compact Routing Scheme for Chordal Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1274-02}, MONTH = may, YEAR = 2002, KEYWORDS = {compact routing, chordal} } @INPROCEEDINGS{FG02, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {A Space Lower Bound for Routing in Trees}, BOOKTITLE = {$19^{th}$ Annual Symposium on Theoretical Aspects of Computer Science (STACS)}, PUBLISHER = {Springer}, VOLUME = {2285 of Lecture Notes in Computer Science}, PAGES = {65-75}, MONTH = mar, YEAR = 2002, KEYWORDS = {compact routing, tree} } @ARTICLE{CFG02, AUTHOR = {Cohen, Johanne and Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Recognizing {K}n{\"o}del Graphs}, JOURNAL = {Discrete Mathematics}, VOLUME = 250, NUMBER = {1-3}, PAGES = {41-62}, YEAR = 2002, KEYWORDS = {recognizing} } %------ 2001 --------------------------------------------------------- @TECHREPORT{Gav01a, AUTHOR = {Gavoille, Cyril}, TITLE = {A Note on Implicit Representation of Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1268-01}, MONTH = dec, YEAR = 2001, KEYWORDS = {labeling scheme} } @TECHREPORT{GP01c, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Distance Labeling Scheme and Split Decomposition}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1263-01}, MONTH = nov, YEAR = 2001, KEYWORDS = {distance labeling} } @INPROCEEDINGS{GP01a, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Split Decomposition and Distance Labelling: {A}n Optimal Scheme for Distance Hereditary Graphs}, BOOKTITLE = {European Conference on Combinatorics, Graph Theory and Applications (COMB)}, EDITOR = {Jaroslav Ne\v{s}et\v{r}il, Marc Noy and Oriol Serra}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 10, PAGES = {117-120}, MONTH = nov, YEAR = 2001, KEYWORDS = {distance labeling}, DOI = {10.1016/S1571-0653(04)00374-9} } @TECHREPORT{FG01c, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {A Space Lower Bound for Routing in Trees}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1262-01}, MONTH = sep, YEAR = 2001, KEYWORDS = {compact routing, tree} } @TECHREPORT{AGKR01, AUTHOR = {Alstrup, Stephen and Gavoille, Cyril and Kaplan, Haim and Rauhe, Theis}, TITLE = {Identifying Nearest Common Ancestors in a Distributed Environment}, INSTITUTION= {The IT University of Copenhagen}, NUMBER = {IT-C Series 2001-6, ISSN 1600-6100}, MONTH = aug, YEAR = 2001, KEYWORDS = {labeling scheme, nca} } @TECHREPORT{GP01b, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {Compact and Localized Distributed Data Structures}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1261-01}, MONTH = aug, YEAR = 2001, KEYWORDS = {labeling scheme, data-structure} } @INPROCEEDINGS{GKKPP01, AUTHOR = {Gavoille, Cyril and Katz, Michal and Katz, Nir A. and Paul, Christophe and Peleg, David}, TITLE = {Approximate Distance Labeling Schemes}, BOOKTITLE = {$9^{th}$ Annual European Symposium on Algorithms (ESA)}, EDITOR = {F. Meyer auf der Heide}, PUBLISHER = {Springer}, VOLUME = {2161 of Lecture Notes in Computer Science}, PAGES = {476-488}, MONTH = aug, YEAR = 2001, KEYWORDS = {distance labeling} } @ARTICLE{FGM01, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Mans, Bernard}, TITLE = {Interval Routing Schemes Allow Broadcasting with Linear Message-Complexity}, JOURNAL = {Distributed Computing}, VOLUME = 14, PAGES = {217-229}, MONTH = jul, YEAR = 2001, KEYWORDS = {interval routing, broadcast} } @INPROCEEDINGS{FG01a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Routing in Trees}, BOOKTITLE = {$28^{th}$ International Colloquium on Automata, Languages and Programming (ICALP)}, EDITOR = {Orejas, Fernando and Spirakis, Paul G. and Leeuwen, Jan van}, PUBLISHER = {Springer}, VOLUME = {2076 of Lecture Notes in Computer Science}, PAGES = {757-772}, MONTH = jul, YEAR = 2001, KEYWORDS = {compact routing, tree} } @INPROCEEDINGS{GPRS01, AUTHOR = {Gavoille, Cyril and Peleg, David and Raspaud, Andr{\'e} and Sopena, Eric}, TITLE = {Small $k$-Dominating Sets in Planar Graphs with Applications}, BOOKTITLE = {$27^{th}$ International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, PUBLISHER = {Springer}, VOLUME = {2204 of Lecture Notes in Computer Science}, PAGES = {201-216}, MONTH = jun, YEAR = 2001, KEYWORDS = {dominating, planar, interval routing} } @INPROCEEDINGS{i:Gav01, AUTHOR = {Gavoille, Cyril}, TITLE = {Compact and Distributed Data Structures (invited lecture)}, BOOKTITLE = {IWIN-SIROCCO~'01 joint conference}, LOCATION = {Vall de Nuria, Spain}, MONTH = jun, YEAR = 2001, KEYWORDS = {compact routing, labeling scheme} } @INPROCEEDINGS{FG01b, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Comment router dans un arbre ?}, BOOKTITLE = {$3^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {INRIA}, PAGES = {85-88}, MONTH = may, YEAR = 2001, KEYWORDS = {compact routing, tree} } @INPROCEEDINGS{DG01, AUTHOR = {Dourisboure, Yon and Gavoille, Cyril}, TITLE = {Interval Routing for Generalized {H}ypercube-Like Graphs}, BOOKTITLE = {$3^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {INRIA}, PAGES = {61-68}, MONTH = may, YEAR = 2001, KEYWORDS = {interval routing} } @TECHREPORT{GPRS01a, AUTHOR = {Gavoille, Cyril and Peleg, David and Raspaud, Andr{\'e} and Sopena, Eric}, TITLE = {Small $k$-Dominating Sets in Planar Graphs with Applications}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1258-01}, MONTH = may, YEAR = 2001, KEYWORDS = {dominating, planar, interval routing} } @ARTICLE{Gav01, AUTHOR = {Gavoille, Cyril}, TITLE = {Routing in Distributed Networks: Overview and Open Problems}, JOURNAL = {ACM SIGACT News - Distributed Computing Column}, VOLUME = 32, NUMBER = 1, PAGES = {36-52}, MONTH = mar, YEAR = 2001, KEYWORDS = {compact routing} } @TECHREPORT{FG01, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Routing in Trees}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1252-01}, MONTH = jan, YEAR = 2001, KEYWORDS = {compact routing, tree} } @INPROCEEDINGS{GPPR01, AUTHOR = {Gavoille, Cyril and Peleg, David and P\'{e}renn\`{e}s, St\'{e}phane and Raz, Ran}, TITLE = {Distance Labeling in Graphs}, BOOKTITLE = {$12^{th}$ Symposium on Discrete Algorithms (SODA)}, PUBLISHER = {ACM-SIAM}, PAGES = {210-219}, MONTH = jan, YEAR = 2001, KEYWORDS = {distance labeling} } @ARTICLE{GP01, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {The Compactness of Interval Routing for Almost All Graphs}, JOURNAL = {SIAM Journal on Computing}, VOLUME = 31, NUMBER = 3, PAGES = {706-721}, YEAR = 2001, KEYWORDS = {interval routing, compact routing} } @ARTICLE{GG01, AUTHOR = {Gavoille, Cyril and Gengler, Marc}, TITLE = {Space-Efficiency of Routing Schemes of Stretch Factor Three}, JOURNAL = {Journal of Parallel and Distributed Computing}, VOLUME = 61, NUMBER = 5, PAGES = {679-687}, YEAR = 2001, KEYWORDS = {compact routing}, DOI = {10.1006/jpdc.2000.1705} } %------ 2000 --------------------------------------------------------- @TECHREPORT{GKKPP00, AUTHOR = {Gavoille, Cyril and Katz, Michal and Katz, Nir A. and Paul, Christophe and Peleg, David}, TITLE = {Approximate Distance Labeling Schemes}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1250-00}, MONTH = dec, YEAR = 2000, KEYWORDS = {distance labeling} } @MISC{Gav00b, AUTHOR = {Gavoille, Cyril}, TITLE = {Structures de donn\'ees compactes et distribu\'ees}, NOTE = {Th{\`e}se d'habilitation à diriger les recherches, Universit{\'e} de Bordeaux}, MONTH = dec, YEAR = 2000, KEYWORDS = {labeling scheme, compact routing, interval routing} } @INPROCEEDINGS{BFGMR00, AUTHOR = {Barri\`{e}re, Lali and Fraigniaud, Pierre and Gavoille, Cyril and Mans, Bernard and Robson, John Michael}, TITLE = {On Recognizing {C}ayley Graphs}, BOOKTITLE = {$8^{th}$ Annual European Symposium on Algorithms (ESA)}, PUBLISHER = {Springer}, VOLUME = {1879 of Lecture Notes in Computer Science}, PAGES = {76-87}, MONTH = sep, YEAR = 2000, KEYWORDS = {cayley, recognizing} } @INPROCEEDINGS{FGM00a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Mans, Bernard}, TITLE = {Interval Routing Schemes Allow Broadcasting with Linear Message-Complexity}, BOOKTITLE = {$19^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, PAGES = {11-20}, MONTH = jul, YEAR = 2000, KEYWORDS = {interval routing, broadcast} } @INPROCEEDINGS{GP00, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Approximate Distance Labeling Schemes}, BOOKTITLE = {$6^{th}$ International Conference on Graph Theory (ICGT)}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 5, PAGES = {134-137}, MONTH = jul, YEAR = 2000, KEYWORDS = {distance labeling}, DOI = {10.1016/S1571-0653(05)80145-3} } @INPROCEEDINGS{GZ00a, AUTHOR = {Gavoille, Cyril and Zemmari, Akka}, TITLE = {The Compactness of Adaptive Routing Tables}, BOOKTITLE = {$7^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, EDITOR = {Flammini, Michele and Nardelli, Enrico and Proietti, Guido and Spirakis, Paul}, PUBLISHER = {Carleton Scientific}, PAGES = {127-140}, MONTH = jun, YEAR = 2000, KEYWORDS = {interval routing} } @TECHREPORT{GPPR00, AUTHOR = {Gavoille, Cyril and Peleg, David and P\'{e}renn\`{e}s, St\'{e}phane and Raz, Ran}, TITLE = {Distance Labeling in Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1239-00}, YEAR = 2000, MONTH = apr, KEYWORDS = {distance labeling} } @TECHREPORT{GZ00, AUTHOR = {Gavoille, Cyril and Zemmari, Akka}, TITLE = {The Compactness of Adaptive Routing Tables}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1233-00}, MONTH = feb, YEAR = 2000, KEYWORDS = {interval routing} } @TECHREPORT{FGM00, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Mans, Bernard}, TITLE = {Interval Routing Schemes Allow Broadcasting with Linear Message-Complexity}, INSTITUTION= {LRI}, ADDRESS = {Universit\'{e} Paris-Sud, 91405 Orsay cedex, France}, TYPE = {{Research Report}}, NUMBER = {LRI-1241}, MONTH = jan, YEAR = 2000, KEYWORDS = {interval routing, broadcast} } @TECHREPORT{CFG00, AUTHOR = {Cohen, Johanne and Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Recognizing {K}n{\"o}del and {F}ibonacci Graphs}, INSTITUTION= {LRI}, ADDRESS = {Universit\'{e} Paris-Sud, 91405 Orsay cedex, France}, NUMBER = {LRI-1238}, TYPE = {{Research Report}}, MONTH = jan, YEAR = 2000, KEYWORDS = {recognizing} } @TECHREPORT{BFGM00, AUTHOR = {Barri\`{e}re, Lali and Fraigniaud, Pierre and Gavoille, Cyril and Mans, Bernard}, TITLE = {Recognizing Abelian {C}ayley Colored Digraphs}, INSTITUTION= {LRI}, ADDRESS = {Universit\'{e} Paris-Sud, 91405 Orsay cedex, France}, TYPE = {{Research Report}}, NUMBER = {LRI-1242}, MONTH = jan, YEAR = 2000, KEYWORDS = {cayley, recognizing} } @ARTICLE{Gav00a, AUTHOR = {Gavoille, Cyril}, TITLE = {On the Dilation of Interval Routing}, JOURNAL = {The Computer Journal}, VOLUME = 43, NUMBER = 1, PAGES = {1-7}, YEAR = 2000, KEYWORDS = {interval routing} } @ARTICLE{Gav00, AUTHOR = {Gavoille, Cyril}, TITLE = {A Survey On Interval Routing}, JOURNAL = {Theoretical Computer Science}, VOLUME = 245, NUMBER = 2, PAGES = {217-253}, YEAR = 2000, KEYWORDS = {interval routing} } %------ 1999 --------------------------------------------------------- @ARTICLE{GP99, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {The Compactness of Interval Routing}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = 12, NUMBER = 4, PAGES = {459-473}, MONTH = oct, YEAR = 1999, KEYWORDS = {interval routing, compact routing} } @INPROCEEDINGS{GH99, AUTHOR = {Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Compact Routing Tables for Graphs of Bounded Genus}, BOOKTITLE = {$26^{th}$ International Colloquium on Automata, Languages and Programming (ICALP)}, EDITOR = {Wiedermann, Ji\v{r}\'{\i} and van Emde Boas, Peter and Nielsen, Mogens}, PUBLISHER = {Springer}, VOLUME = {1644 of Lecture Notes in Computer Science}, PAGES = {351-360}, MONTH = jul, YEAR = 1999, KEYWORDS = {compact routing} } @BOOK{GBR99, AUTHOR = {Gavoille, Cyril and Bermond, Jean-Claude and Raspaud, Andr{\'e}}, TITLE = {Proceedings of the $6^{th}$ International Colloquium on Structural Information \& Communication Complexity, SIROCCO 6}, PUBLISHER = {Carleton Scientific}, ISBN = {1-894145-04-6}, MONTH = jul, YEAR = 1999, KEYWORDS = {misc graph} } @INPROCEEDINGS{CFG99, AUTHOR = {Cohen, Johanne and Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Recognizing Bipartite Incident-Graphs of Circulant Digraphs}, BOOKTITLE = {$25^{th}$ International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, PUBLISHER = {Springer}, EDITOR = {Widmayer, Peter and Neyer, Gabriele and Eidenbenz, Stephan}, VOLUME = {1665 of Lecture Notes in Computer Science}, PAGES = {215-227}, MONTH = jun, YEAR = 1999, KEYWORDS = {recognizing} } @INPROCEEDINGS{GH99b, AUTHOR = {Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Routage compact dans les r\'eseaux de genre born\'e}, BOOKTITLE = {$1^{\mbox{\`ere}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {INRIA}, PAGES = {1-5}, MONTH = may, YEAR = 1999, KEYWORDS = {compact routing} } @TECHREPORT{GH99a, AUTHOR = {Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {Compact Routing Tables for Graphs of Bounded Genus}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1213-99}, MONTH = feb, YEAR = 1999, KEYWORDS = {compact routing} } %------ 1998 --------------------------------------------------------- @INPROCEEDINGS{GP98a, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {The Compactness of Interval Routing for Almost All Graphs}, BOOKTITLE = {$12^{th}$ International Symposium on Distributed Computing (DISC)}, EDITOR = {Kutten, Shay}, PUBLISHER = {Springer}, VOLUME = {1499 of Lecture Notes in Computer Science}, PAGES = {161-174}, MONTH = sep, YEAR = 1998, KEYWORDS = {interval routing, compact routing} } @INPROCEEDINGS{EGP98a, AUTHOR = {Eilam, Tamar and Gavoille, Cyril and Peleg, David}, TITLE = {Compact Routing Schemes With Low Stretch Factor}, BOOKTITLE = {$17^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, PAGES = {11-20}, MONTH = aug, YEAR = 1998, KEYWORDS = {compact routing, interval routing} } @INPROCEEDINGS{FG98b, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {A Theoretical Model for Routing Complexity}, BOOKTITLE = {$5^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, EDITOR = {Gargano, Luisa and Peleg, David}, PUBLISHER = {Carleton Scientific}, PAGES = {98-113}, MONTH = jul, YEAR = 1998, KEYWORDS = {compact routing} } @TECHREPORT{GP98, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {The Compactness of Interval Routing for Almost All Graphs}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1202-98}, MONTH = apr, YEAR = 1998, KEYWORDS = {interval routing, compact routing} } @ARTICLE{FG98a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Interval Routing Schemes}, JOURNAL = {Algorithmica}, VOLUME = 21, PAGES = {155-182}, YEAR = 1998, KEYWORDS = {interval routing} } @TECHREPORT{EGP98, AUTHOR = {Eilam, Tamar and Gavoille, Cyril and Peleg, David}, TITLE = {Compact Routing Schemes With Low Stretch Factor}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1195-98}, MONTH = jan, YEAR = 1998, KEYWORDS = {compact routing, interval routing} } @ARTICLE{GG98, AUTHOR = {Gavoille, Cyril and Gu\'{e}vremont, Eric}, TITLE = {Worst Case Bounds For Shortest Path Interval Routing}, JOURNAL = {Journal of Algorithms}, VOLUME = 27, NUMBER = 1, PAGES = {1-25}, YEAR = 1998, KEYWORDS = {interval routing} } %------ 1997 --------------------------------------------------------- @TECHREPORT{GG97a, AUTHOR = {Gavoille, Cyril and Gengler, Marc}, TITLE = {Space-Efficiency of Routing Schemes of Stretch Factor Three}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1181-97}, MONTH = oct, YEAR = 1997, KEYWORDS = {compact routing} } @TECHREPORT{Gav97a, AUTHOR = {Gavoille, Cyril}, TITLE = {A Survey On Interval Routing Scheme}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1182-97}, MONTH = oct, YEAR = 1997, KEYWORDS = {interval routing} } @TECHREPORT{GP97, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {The Compactness of Interval Routing}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1176-97}, MONTH = sep, YEAR = 1997, KEYWORDS = {interval routing, compact routing} } @INPROCEEDINGS{Gav97, AUTHOR = {Gavoille, Cyril}, TITLE = {On the Dilation of Interval Routing}, BOOKTITLE = {$22^{nd}$ International Symposium on Mathematical Foundations of Computer Science (MFCS)}, EDITOR = {Pr{\'{\i}}vara, Igor and Ru{\v{z}}i{\v{c}}ka, Peter}, PUBLISHER = {Springer}, VOLUME = {1300 of Lecture Notes in Computer Science}, PAGES = {259-268}, MONTH = aug, YEAR = 1997, DOI = {10.1007/BFb0029943}, KEYWORDS = {interval routing} } @INPROCEEDINGS{GG97, AUTHOR = {Gavoille, Cyril and Gengler, Marc}, TITLE = {Space-Efficiency of Routing Schemes of Stretch Factor Three}, BOOKTITLE = {$4^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, EDITOR = {Krizanc, Danny and Widmayer, Peter}, PUBLISHER = {Carleton Scientific}, PAGES = {162-175}, MONTH = jul, YEAR = 1997, KEYWORDS = {compact routing} } @INPROCEEDINGS{i:Gav97, AUTHOR = {Gavoille, Cyril}, TITLE = {Compact Routing: Lower Bounds Techniques (invited lecture)}, BOOKTITLE = {International Research School on "Sense of Direction and Compact Routing"}, LOCATION = {Siena, Italy}, MONTH = jun, YEAR = 1997, KEYWORDS = {interval routing} } @ARTICLE{FG97, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Universal Routing Schemes}, JOURNAL = {Distributed Computing}, PUBLISHER = {Springer-Verlag}, VOLUME = 10, PAGES = {65-78}, YEAR = 1997, KEYWORDS = {compact routing} } %------ 1996 --------------------------------------------------------- @TECHREPORT{Gav96c, AUTHOR = {Gavoille, Cyril}, TITLE = {On Dilation of Interval Routing}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1145-96}, YEAR = 1996, MONTH = nov, KEYWORDS = {interval routing} } @TECHREPORT{Gav96b, AUTHOR = {Gavoille, Cyril}, TITLE = {Lower Bounds for Interval Routing on Bounded Degree Networks}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib\'{e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1144-96}, NOTE = {Submitted for publication}, MONTH = oct, YEAR = 1996, KEYWORDS = {interval routing} } @INPROCEEDINGS{FG96a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Local Memory Requirement of Universal Routing Schemes}, BOOKTITLE = {$8^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, PAGES = {183-188}, MONTH = jun, YEAR = 1996, KEYWORDS = {compact routing} } @INPROCEEDINGS{GP96, AUTHOR = {Gavoille, Cyril and P\'{e}renn\`{e}s, St\'{e}phane}, TITLE = {Lower Bounds for Interval Routing on $3$-Regular Networks}, BOOKTITLE = {$3^{rd}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, EDITOR = {Santoro, Nicola and Spirakis, Paul}, PUBLISHER = {Carleton University Press}, PAGES = {88-103}, MONTH = jun, YEAR = 1996, KEYWORDS = {interval routing} } @INPROCEEDINGS{GP96b, AUTHOR = {Gavoille, Cyril and P\'{e}renn\`{e}s, St\'{e}phane}, TITLE = {Memory Requirement for Routing in Distributed Networks}, BOOKTITLE = {$15^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, PAGES = {125-133}, YEAR = 1996, MONTH = may, KEYWORDS = {compact routing} } @TECHREPORT{GP96a, AUTHOR = {Gavoille, Cyril and P\'{e}renn\`{e}s, St\'{e}phane}, TITLE = {Lower Bounds for Shortest Path Interval Routing}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {96-08}, MONTH = apr, YEAR = 1996, KEYWORDS = {interval routing} } @PHDTHESIS{Gav96, AUTHOR = {Gavoille, Cyril}, TITLE = {Complexit\'{e} m\'{e}moire du routage dans les r\'{e}seaux distribu\'{e}s}, SCHOOL = {{\'E}cole {N}ormale {S}up\'{e}rieure de {L}yon}, ADDRESS = {46, all\'{e}e d'{I}talie}, MONTH = jan, YEAR = 1996, KEYWORDS = {compact routing, interval routing} } @TECHREPORT{FG96, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Local Memory Requirement of Universal Routing Schemes}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {96-01}, MONTH = jan, YEAR = 1996, KEYWORDS = {compact routing} } %------ 1995 --------------------------------------------------------- @TECHREPORT{GP95a, AUTHOR = {Gavoille, Cyril and P\'{e}renn\`{e}s, St\'{e}phane}, TITLE = {Memory Requirement for Routing in Distributed Networks}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {95-46}, MONTH = dec, YEAR = 1995, KEYWORDS = {compact routing} } @INPROCEEDINGS{FG95a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Memory Requirement for Universal Routing Schemes}, BOOKTITLE = {$14^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, PAGES = {223-230}, MONTH = aug, YEAR = 1995, KEYWORDS = {compact routing} } @TECHREPORT{GP95, AUTHOR = {Gavoille, Cyril and P\'{e}renn\`{e}s, St\'{e}phane}, TITLE = {Routing Memory Requirement for Distributed Networks}, INSTITUTION= {I3S}, ADDRESS = {Universit\'{e} de Nice-Sophia Antipolis, 06903 Sophia Antipolis, France}, TYPE = {{Research Report}}, NUMBER = {95-37}, MONTH = aug, YEAR = 1995, KEYWORDS = {compact routing} } @INPROCEEDINGS{GG95a, AUTHOR = {Gavoille, Cyril and Gu\'{e}vremont, Eric}, TITLE = {On the Compactness of Bounded Degree Graphs for Shortest Path Interval Routing}, BOOKTITLE = {$2^{nd}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, PUBLISHER = {Carleton University Press}, PAGES = {113-121}, MONTH = jun, YEAR = 1995, KEYWORDS = {interval routing} } @TECHREPORT{FG95, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Memory Requirement for Universal Routing Schemes}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {95-05}, MONTH = mar, YEAR = 1995, KEYWORDS = {compact routing} } @TECHREPORT{GG95, AUTHOR = {Gavoille, Cyril and Gu\'{e}vremont, Eric}, TITLE = {Worst Case Bounds For Shortest Path Interval Routing}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {95-02}, MONTH = jan, YEAR = 1995, KEYWORDS = {interval routing} } %------ 1994 --------------------------------------------------------- @INPROCEEDINGS{FG94a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Optimal Interval Routing}, BOOKTITLE = {Parallel Processing: CONPAR~'94 - VAPP~VI}, PUBLISHER = {Springer-Verlag}, EDITOR = {Buchberger, Bruno and Volkert, Jens}, VOLUME = {854 of Lecture Notes in Computer Science}, PAGES = {785-796}, MONTH = sep, YEAR = 1994, KEYWORDS = {interval routing} } @INPROCEEDINGS{FG94c, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {A Characterization of Networks supporting Linear Interval Routing}, BOOKTITLE = {$13^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, PAGES = {216-224}, MONTH = aug, YEAR = 1994, KEYWORDS = {interval routing} } @INPROCEEDINGS{Gav94, AUTHOR = {Gavoille, Cyril}, TITLE = {Routages efficaces et compacts}, ADDRESS = {LIP, \'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, BOOKTITLE = {$6^{\mbox{\`emes}}$ Rencontres Francophones du Parall\'{e}lisme (RenPar)}, EDITOR = {Luc Boug\'{e} and Michel Cosnard and Pierre Fraigniaud}, MONTH = jun, PAGES = {298}, YEAR = 1994, DATE = {7-10 juin 1994}, KEYWORDS = {interval routing, compact routing} } @TECHREPORT{FG94, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Interval Routing Schemes}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, TYPE = {{Research Report}}, NUMBER = {94-04}, MONTH = jan, YEAR = 1994, KEYWORDS = {interval routing} } %------ 1993 --------------------------------------------------------- @ARTICLE{DGJP93a, AUTHOR = {Desprez, Fr\'{e}d\'{e}ric and Gavoille, Cyril and Jargot, Bruno and Pourzandi, Makan}, TITLE = {Tests des performances des communications de la machine {V}olvox~{IS}-860}, JOURNAL = {La lettre du Transputer et des Calculateurs Parall\`{e}les}, VOLUME = 19, PAGES = {11-35}, MONTH = oct, YEAR = 1993, KEYWORDS = {routing, parallel} } @MASTERSTHESIS{Gav93, AUTHOR = {Gavoille, Cyril}, TITLE = {Routage par Intervalles}, SCHOOL = {\'{E}cole Normale Sup\'{e}rieure de Lyon}, ADDRESS = {69364 Lyon Cedex 07, France}, TYPE = {Stage de {DEA}}, DATE = {28 juin 1993}, MONTH = jun, YEAR = 1993, KEYWORDS = {interval routing} } @TECHREPORT{DGJP93, AUTHOR = {Desprez, Fr\'{e}d\'{e}ric and Gavoille, Cyril and Jargot, Bruno and Pourzandi, Makan}, TITLE = {Tests des performances des communications de la machine {V}olvox~{IS}-860}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, NUMBER = {93-02}, MONTH = mar, YEAR = 1993, KEYWORDS = {routing, parallel} } %------ 1992 --------------------------------------------------------- @TECHREPORT{Gav92, AUTHOR = {Gavoille, Cyril}, TITLE = {Evaluation of the {M}as{P}ar {MP}-1 Performances}, INSTITUTION= {LIP}, ADDRESS = {\'{E}cole Normale Sup\'{e}rieure de Lyon, 69364 Lyon Cedex 07, France}, NUMBER = {92-01}, MONTH = feb, YEAR = 1992, KEYWORDS = {parallel} }