%------ 2012 --------------------------------------------------------- @INPROCEEDINGS{ACG12, AUTHOR = {Abraham, Ittai and Chechik, Shiri and Gavoille, Cyril}, TITLE = {Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels}, BOOKTITLE = {$44^{th}$ Annual ACM Symposium on Theory of Computing (STOC)}, PUBLISHER = {ACM Press}, LOCATION = {New York, NY, USA}, MONTH = may, YEAR = 2012, KEYWORDS = {data-structure, dynamic, planar, compact routing} } @TECHREPORT{BGHP12, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Perkovi{\'c}, Ljubomir}, TITLE = {The Stretch Factor of ${L}_1$- and ${L}_\infty$-{D}elaunay Triangulations}, INSTITUTION= {HAL/arXiv}, NUMBER = {hal-00673187v2/1202.5127v2 [cs.GC]}, MONTH = feb, YEAR = 2012, KEYWORDS = {triangulation, spanner} } %------ 2011 --------------------------------------------------------- @INPROCEEDINGS{GGV11, AUTHOR = {Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent}, TITLE = {Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners}, BOOKTITLE = {$15^{th}$ International Conference on Principles of Distributed Systems (OPODIS)}, PUBLISHER = {Springer}, LOCATION = {Toulouse, France}, VOLUME = {7109 of Lecture Notes in Computer Science}, PAGES = {143-158}, MONTH = dec, YEAR = 2011, KEYWORDS = {spanner}, DOI = {10.1007/978-3-642-25873-2_11} } @INPROCEEDINGS{i:Gav11b, AUTHOR = {Gavoille, Cyril}, TITLE = {Dynamic Algorithms via Forbidden-Set Labeling}, BOOKTITLE = {First International Workshop on Dynamic Systems (DYNAM)}, LOCATION = {LAAS, Toulouse}, MONTH = dec, YEAR = 2011, KEYWORDS = {dynamic, labeling scheme} } @INPROCEEDINGS{talk:Gav11b, AUTHOR = {Gavoille, Cyril}, TITLE = {A Quick Overview on Name-Independent Compact Routing Schemes}, BOOKTITLE = {Euler Project Meeting}, LOCATION = {Barcelone, Spain}, MONTH = nov, YEAR = 2011, KEYWORDS = {compact routing} } @INPROCEEDINGS{AG11, AUTHOR = {Abraham, Ittai and Gavoille, Cyril}, TITLE = {On Approximate Distance Labels and Routing Schemes with Affine Stretch}, BOOKTITLE = {$25^{th}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, LOCATION = {Rome, Italy}, VOLUME = {6950 of Lecture Notes in Computer Science (ARCoSS)}, PAGES = {404-415}, MONTH = sep, YEAR = 2011, KEYWORDS = {distance labeling, compact routing}, DOI = {10.1007/978-3-642-24100-0_39} } @TECHREPORT{GGV11a, AUTHOR = {Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent}, TITLE = {Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners}, INSTITUTION= {HAL}, NUMBER = {hal-00622915}, MONTH = sep, YEAR = 2011, KEYWORDS = {spanner} } @INCOLLECTION{BGH11, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {An Information-Theoretic Upper Bound on Planar Graphs Using Well-orderly Maps}, BOOKTITLE = {Towards an Information Theory of Complex Networks}, PUBLISHER = {Birkh\"auser Boston}, EDITOR = {Dehmer, Matthias and Emmert-Streib, Frank and Mehler, Alexander}, CHAPTER = 2, PAGES = {17-46}, MONTH = jul, YEAR = 2011, ISBN-13 = {978-0-8176-4904-3}, KEYWORDS = {planar, counting, coding}, DOI = {10.1007/978-0-8176-4904-3_2} } @INPROCEEDINGS{GS11, AUTHOR = {Gavoille, Cyril and Sommer, Christian}, TITLE = {Sparse Spanners vs. Compact Routing}, BOOKTITLE = {$23^{rd}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {San Jose, CA, USA}, PAGES = {225-234}, MONTH = jun, YEAR = 2011, KEYWORDS = {compact routing, minor, planar}, DOI = {10.1145/1989493.1989526} } @INPROCEEDINGS{DGO11, AUTHOR = {Diot, \'Emilie and Gavoille, Cyril and Ochem, Pascal}, TITLE = {Sur la difficulté de séparer un graphe par des plus courts chemins}, BOOKTITLE = {$13^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {HAL}, LOCATION = {Cap Estérel, France}, VOLUME = {inria-00588312}, PAGES = {65-72}, MONTH = may, YEAR = 2011, KEYWORDS = {separator} } @ARTICLE{DG11, AUTHOR = {Dieng, Youssou and Gavoille, Cyril}, TITLE = {Routage compact optimal dans les $(k,r)$-constellations}, JOURNAL = {Technique et Science Informatiques}, PUBLISHER = {Hermes Science Publications -- Lavoisier}, VOLUME = 30, NUMBER = {n$^o$ 5/2011}, PAGES = {485-513}, MONTH = may, YEAR = 2011, KEYWORDS = {compact routing, outerplanar, minor}, DOI = {10.3166/TSI.30.485-513} } @INPROCEEDINGS{i:Gav11, AUTHOR = {Gavoille, Cyril}, TITLE = {Oracles pour les arbres et les graphes}, BOOKTITLE = {10 ans du s\'eminaire MaMux - Math\'ematiques, musique et relations avec d'autres disciplines}, LOCATION = {IRCAM, Paris}, MONTH = may, YEAR = 2011, KEYWORDS = {distance labeling} } @INPROCEEDINGS{talk:Gav11, AUTHOR = {Gavoille, Cyril}, TITLE = {Spanner, Distance Oracle, and Compact Routing for Unweighted Graphs}, BOOKTITLE = {ANR Aladdin Meeting}, LOCATION = {Arcachon, France}, MONTH = may, YEAR = 2011, KEYWORDS = {distance labeling, compact routing} } @TECHREPORT{GGHIM11, AUTHOR = {Gavoille, Cyril and Glacet, Christian and Hanusse, Nicolas and Ilcinkas, David and Majorczyk, Fr\'ed\'eric}, TITLE = {Simulations de routage du sch\'ema {AGMaNT}}, INSTITUTION= {LaBRI, Universit\'e Bordeaux}, TYPE = {Rapport de contrat (final)}, NUMBER = {DCR - Alcaltel-Lucent Bell}, MONTH = feb, YEAR = 2011, KEYWORDS = {contract, compact routing} } @ARTICLE{CGK11, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mamadou Mustapha}, TITLE = {Compact Labelings For Efficient First-Order Model-Checking}, JOURNAL = {Journal of Combinatorial Optimization}, VOLUME = 21, NUMBER = 1, PAGES = {19-46}, MONTH = jan, YEAR = 2011, KEYWORDS = {logic, labeling scheme}, DOI = {10.1007/s10878-009-9260-7} } %------ 2010 --------------------------------------------------------- @INPROCEEDINGS{DG10b, AUTHOR = {Diot, \'Emilie and Gavoille, Cyril}, TITLE = {La Hi\'erarchie des graphes $k$-chemin s\'eparables}, BOOKTITLE = {$12^{\mbox{\`emes}}$ Journ\'ees Graphes et Algorithmes}, LOCATION = {CIRM, Marseille, France}, PAGES = 7, MONTH = nov, YEAR = 2010, KEYWORDS = {planar, minor} } @ARTICLE{AGMW10, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Wieder, Udi}, TITLE = {Strong-Diameter Decompositions of Minor Free Graphs}, JOURNAL = {Theory of Computing Systems}, PUBLISHER = {Springer}, VOLUME = 47, NUMBER = 4, PAGES = {837-855}, MONTH = nov, YEAR = 2010, KEYWORDS = {decomposition, planar, minor, compact routing}, DOI = {10.1007/s00224-010-9283-6} } @INPROCEEDINGS{GGV10b, AUTHOR = {Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent}, TITLE = {Spanners additifs de taille sous-quadratique pour les graphes orient\'es}, BOOKTITLE = {$12^{\mbox{\`emes}}$ Journ\'ees Graphes et Algorithmes}, LOCATION = {CIRM, Marseille, France}, PAGES = 9, MONTH = nov, YEAR = 2010, KEYWORDS = {spanner} } @ARTICLE{GPSS10, AUTHOR = {Gavoille, Cyril and Patt-Shamir, Boaz and Scheideler, Christian}, TITLE = {Special Issue: {P}arallelism on {A}lgorithms and {A}rchitectures ({SPAA)}}, JOURNAL = {Theory of Computing Systems}, PUBLISHER = {Springer}, VOLUME = 47, NUMBER = 4, PAGES = {809-962}, MONTH = nov, YEAR = 2010, KEYWORDS = {distributed, parallel}, DOI = {10.1007/s00224-010-9284-5} } @TECHREPORT{DG10a, AUTHOR = {Diot, \'Emilie and Gavoille, Cyril}, TITLE = {Path Separability of Graphs}, INSTITUTION= {HAL}, NUMBER = {hal-00507833}, MONTH = sep, YEAR = 2010, KEYWORDS = {planar, minor} } @INPROCEEDINGS{DG10, AUTHOR = {Diot, \'Emilie and Gavoille, Cyril}, TITLE = {Path Separability of Graphs}, BOOKTITLE = {$4^{th}$ International Frontiers of Algorithmics Workshop (FAW)}, LOCATION = {Wuhan, China}, PUBLISHER = {Springer}, VOLUME = {6213 of Lecture Notes in Computer Science}, PAGES = {262-273}, MONTH = aug, YEAR = 2010, KEYWORDS = {planar, minor}, DOI = {10.1007/978-3-642-14553-7_25} } @BOOK{AGKMS10, AUTHOR = {Abramsky, Sansom and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul}, TITLE = {Proceedings of the $37^{th}$ International Colloquium on Automata, Languages and Programming, ICALP 2010, Bordeaux, France, July 6-10, 2010, Part I \& II}, PUBLISHER = {Springer}, SERIES = {6198 \& 6199 of Lecture Notes in Computer Science (ARCoSS)}, ISBN = {978-3-642-14164-5 \& 978-3-642-14161-4}, MONTH = jul, YEAR = 2010, DOI = {10.1007/978-3-642-14165-2 \& 10.1007/978-3-642-14162-1}, KEYWORDS = {misc} } @INPROCEEDINGS{BGHP10, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Perkovi{\'c}, Ljubomir}, TITLE = {Plane Spanners of Maximum Degree Six}, BOOKTITLE = {$37^{th}$ International Colloquium on Automata, Languages and Programming (ICALP)}, PUBLISHER = {Springer}, VOLUME = {6198 of Lecture Notes in Computer Science (ARCoSS)}, LOCATION = {Bordeaux, France}, PAGES = {19-30}, MONTH = jul, YEAR = 2010, KEYWORDS = {triangulation, planar, spanner}, DOI = {10.1007/978-3-642-14165-2_3} } @INPROCEEDINGS{ACGP10, AUTHOR = {Abraham, Ittai and Chechik, Shiri and Gavoille, Cyril and Peleg, David}, TITLE = {Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension}, BOOKTITLE = {$29^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, LOCATION = {Z{\"u}rich, Switzerland}, PAGES = {192-200}, MONTH = jul, YEAR = 2010, KEYWORDS = {compact routing, forbidden, oracle}, DOI = {10.1145/1835698.1835743} } @INPROCEEDINGS{BGHIP10, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Ilcinkas, David and Perkovi{\'c}, Ljubomir}, TITLE = {Comment r\'esumer le plan}, BOOKTITLE = {$12^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {HAL}, LOCATION = {Belle Dune, C\^ote d'Opale, France}, VOLUME = {inria-00476151}, MONTH = jun, YEAR = 2010, KEYWORDS = {triangulation, planar, spanner} } @INPROCEEDINGS{BGHI10, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Ilcinkas, David}, TITLE = {Connections between Theta-Graphs, {D}elaunay Triangulations, and Orthogonal Surfaces}, BOOKTITLE = {$36^{th}$ International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, PUBLISHER = {Springer}, VOLUME = {6410 of Lecture Notes in Computer Science (ARCoSS)}, LOCATION = {Zar\'os, Crete, Greece}, PAGES = {266-278}, MONTH = jun, YEAR = 2010, KEYWORDS = {triangulation, planar, spanner}, DOI = {10.1007/978-3-642-16926-7_25} } @INPROCEEDINGS{GGV10a, AUTHOR = {Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent}, TITLE = {Graphes de recouvrement multichemins}, BOOKTITLE = {$12^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {HAL}, LOCATION = {Belle Dune, C\^ote d'Opale, France}, VOLUME = {inria-00475970}, MONTH = jun, YEAR = 2010, KEYWORDS = {spanner} } @INPROCEEDINGS{GGV10, AUTHOR = {Gavoille, Cyril and Godfroy, Quentin and Viennot, Laurent}, TITLE = {Multipath Spanners}, BOOKTITLE = {$17^{th}$ International Colloquium on Structural Information \& Communication Complexity (SIROCCO)}, LOCATION = {\c{S}irince, Turkey}, PUBLISHER = {Springer}, VOLUME = {6058 of Lecture Notes in Computer Science}, PAGES = {211-223}, MONTH = jun, YEAR = 2010, KEYWORDS = {spanner}, DOI = {10.1007/978-3-642-13284-1_17} } @TECHREPORT{BGHI10a, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Ilcinkas, David}, TITLE = {Connections between Theta-Graphs, {D}elaunay Triangulations, and Orthogonal Surfaces}, INSTITUTION= {HAL}, NUMBER = {hal-00454565}, MONTH = feb, YEAR = 2010, KEYWORDS = {triangulation, planar, spanner} } @TECHREPORT{MKTPG10, AUTHOR = {Markiewicz, Marcin and Kosowski, Adrian and Tylec, Tomasz and Pykacz, Jaros{\l}aw and Gavoille, Cyril}, TITLE = {Static Quantum Games Revisited}, INSTITUTION= {arXiv}, NUMBER = {1001.2257v3 [quant-ph]}, MONTH = jan, YEAR = 2010, NOTE = {Submitted to Physics Letters A}, KEYWORDS = {quantum, game} } %------ 2009 --------------------------------------------------------- @INPROCEEDINGS{DGPV09, AUTHOR = {Derbel, Bilel and Gavoille, Cyril and Peleg, David and Viennot, Laurent}, TITLE = {Local Computation of Nearly Additive Spanners}, BOOKTITLE = {$23^{rd}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, LOCATION = {Elche, Spain}, VOLUME = {5805 of Lecture Notes in Computer Science}, PAGES = {176-190}, MONTH = sep, YEAR = 2009, KEYWORDS = {spanner, distributed}, DOI = {10.1007/978-3-642-04355-0_20} } @INPROCEEDINGS{DG09b, AUTHOR = {Dieng, Youssou and Gavoille, Cyril}, TITLE = {On the Tree-Width of Planar Graphs}, BOOKTITLE = {European Conference on Combinatorics, Graph Theory and Applications (EuroComb)}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 34, PAGES = {593-596}, MONTH = sep, YEAR = 2009, KEYWORDS = {tree-decomposition, planar}, DOI = {10.1016/j.endm.2009.07.099} } @INPROCEEDINGS{DG09a, AUTHOR = {Diot, \'Emilie and Gavoille, Cyril}, TITLE = {On the path separability of planar graphs}, BOOKTITLE = {European Conference on Combinatorics, Graph Theory and Applications (EuroComb)}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 34, PAGES = {549-552}, MONTH = sep, YEAR = 2009, KEYWORDS = {tree-decomposition, planar, distance}, DOI = {10.1016/j.endm.2009.07.091} } @INPROCEEDINGS{GKM09, AUTHOR = {Gavoille, Cyril and Kosowski, Adrian and Markiewicz, Marcin}, TITLE = {What Can be Observed Locally? {R}ound-based Models for Quantum Distributed Computing}, BOOKTITLE = {$23^{rd}$ International Symposium on Distributed Computing (DISC)}, PUBLISHER = {Springer}, LOCATION = {Elche, Spain}, VOLUME = {5805 of Lecture Notes in Computer Science}, PAGES = {243-257}, MONTH = sep, YEAR = 2009, KEYWORDS = {quantum, distributed, coloring}, DOI = {10.1007/978-3-642-04355-0_26} } @ARTICLE{BG09, AUTHOR = {Bazzaro, Fabrice and Gavoille, Cyril}, TITLE = {Localized and Compact Data-Structure for Comparability Graphs}, JOURNAL = {Discrete Mathematics}, VOLUME = 309, NUMBER = 11, PAGES = {3465-3484}, MONTH = jun, YEAR = 2009, KEYWORDS = {data-structure, permutation graph, labeling scheme}, DOI = {10.1016/j.disc.2007.12.091} } @INPROCEEDINGS{Gav09, AUTHOR = {Gavoille, Cyril}, TITLE = {Spanner et routage compact : similarit\'es et diff\'erences}, BOOKTITLE = {$11^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, PUBLISHER = {HAL}, LOCATION = {Carry-Le-Rouet, France}, VOLUME = {inria-00383276}, MONTH = jun, YEAR = 2009, KEYWORDS = {compact routing, spanner} } @ARTICLE{FGKLL09, 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}, JOURNAL = {Theoretical Computer Science}, VOLUME = 410, NUMBER = {21-23}, PAGES = {1970-1981}, MONTH = may, YEAR = 2009, KEYWORDS = {small world, tree-decomposition}, DOI = {10.1016/j.tcs.2008.12.061} } @INPROCEEDINGS{i:Gav09, AUTHOR = {Gavoille, Cyril}, TITLE = {Routing in Distributed Systems (3 invited lectures)}, BOOKTITLE = {$1^{st}$ Workshop on New Challenges in Distributed Systems}, LOCATION = {Valpara{\'\i}so, Chile}, MONTH = apr, YEAR = 2009, KEYWORDS = {compact routing, spanner} } @TECHREPORT{CGKT09, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mamadou Mustapha and Twigg, David Andrew}, TITLE = {Optimal labelling for connectivity checking in planar networks with obstacles}, INSTITUTION= {HAL}, NUMBER = {hal-00367746}, MONTH = mar, YEAR = 2009, KEYWORDS = {labeling scheme, planar, forbidden} } @TECHREPORT{GKM09a, AUTHOR = {Gavoille, Cyril and Kosowski, Adrian and Markiewicz, Marcin}, TITLE = {What Can be Observed Locally? {R}ound-based Models for Quantum Distributed Computing}, INSTITUTION= {arXiv}, NUMBER = {0903.1133v1 [quant-ph]}, MONTH = mar, YEAR = 2009, KEYWORDS = {quantum, distributed, coloring} } @ARTICLE{FGIP09, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Ilcinkas, David and Pelc, Andrzej}, TITLE = {Distributed Computing with Advice: Information Sensitivity of Graph Coloring}, JOURNAL = {Distributed Computing}, PUBLISHER = {Springer-Verlag}, VOLUME = 21, NUMBER = 6, PAGES = {395-403}, MONTH = mar, YEAR = 2009, KEYWORDS = {coloring, distributed}, DOI = {10.1007/s00446-008-0076-y} } @INPROCEEDINGS{DG09, AUTHOR = {Dieng, Youssou and Gavoille, Cyril}, TITLE = {Routage dans les r\'eseaux $(k,r)$-cellulaires}, BOOKTITLE = {$10^{\mbox{\`emes}}$ Journ\'ees Doctorales en Informatique et R\'eseaux (JDIR)}, LOCATION = {Belfort, UTBM, France}, PAGES = {7-12}, MONTH = feb, YEAR = 2009, KEYWORDS = {compact routing, outerplanar, minor} } @ARTICLE{GKKKN09, 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}, JOURNAL = {Networks}, VOLUME = 54, NUMBER = 1, PAGES = {12-19}, YEAR = 2009, KEYWORDS = {coloring, distributed}, DOI = {10.1002/net.20293} } %------ 2008 --------------------------------------------------------- @INPROCEEDINGS{DG08a, AUTHOR = {Dieng, Youssou and Gavoille, Cyril}, TITLE = {La structure des graphes sans mineur ${K}_{2,4}$}, BOOKTITLE = {$10^{\mbox{\`emes}}$ Journ\'ees Graphes et Algorithmes}, LOCATION = {INRIA Sophia-Antipolis, Nice}, MONTH = nov, YEAR = 2008, KEYWORDS = {minor} } @TECHREPORT{CGK08a, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mamadou Mustapha}, TITLE = {Compact Labelings For Efficient First-Order Model-Checking}, INSTITUTION= {HAL}, NUMBER = {hal-00342668}, MONTH = nov, YEAR = 2008, KEYWORDS = {logic, labeling scheme} } @INPROCEEDINGS{DGPV08b, AUTHOR = {Derbel, Bilel and Gavoille, Cyril and Peleg, David and Viennot, Laurent}, TITLE = {On the Locality of Distributed Sparse Spanner Construction}, BOOKTITLE = {$27^{th}$ Annual ACM Symposium on Principles of Distributed Computing (PODC)}, PUBLISHER = {ACM Press}, LOCATION = {Toronto, Canada}, PAGES = {273-282}, MONTH = aug, YEAR = 2008, KEYWORDS = {spanner, distributed}, DOI = {10.1145/1400751.1400788} } @INPROCEEDINGS{CGKT08, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mamadou Mustapha and Twigg, David Andrew}, TITLE = {Connectivity check in 3-connected planar graphs with obstacles}, BOOKTITLE = {International Conference on Topological \& Geometric Graph Theory}, LOCATION = {ENS Paris, France}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 31, PAGES = {151-155}, MONTH = aug, YEAR = 2008, KEYWORDS = {labeling scheme, planar, forbidden}, DOI = {10.1016/j.endm.2008.06.030} } @ARTICLE{GP08, AUTHOR = {Gavoille, Cyril and Paul, Christophe}, TITLE = {Optimal Distance Labeling for Interval Graphs and Related Graphs Families}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = 22, NUMBER = 3, PAGES = {1239-1258}, MONTH = jul, YEAR = 2008, KEYWORDS = {distance labeling, circular-arc, interval graph}, DOI = {10.1137/050635006} } @INPROCEEDINGS{CGK08, AUTHOR = {Courcelle, Bruno and Gavoille, Cyril and Kant\'e, Mamadou Mustapha}, TITLE = {Efficient First-Order Model-Checking using Short Labels}, BOOKTITLE = {$2^{nd}$ International Frontiers of Algorithmics Workshop (FAW)}, PUBLISHER = {Springer}, VOLUME = {5059 of Lecture Notes in Computer Science}, PAGES = {159-170}, LOCATION = {Changsha, China}, MONTH = jun, YEAR = 2008, KEYWORDS = {logic, labeling scheme}, DOI = {10.1007/978-3-540-69311-6_18} } @ARTICLE{AGMNT08, AUTHOR = {Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Nisan, Noam and Thorup, Mikkel}, TITLE = {Compact Name-Independent Routing with Minimum Stretch}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = 3, NUMBER = 4, PAGES = {Article 37}, MONTH = jun, YEAR = 2008, KEYWORDS = {compact routing, name-independent}, DOI = {10.1145/1367064.1367077} } @INPROCEEDINGS{FG08, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Polylogarithmic Network Navigability Using Compact Metrics with Small Stretch}, BOOKTITLE = {$20^{th}$ Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, PUBLISHER = {ACM Press}, LOCATION = {Munich, Germany}, PAGES = {62-69}, MONTH = jun, YEAR = 2008, KEYWORDS = {small world}, DOI = {10.1145/1378533.1378542} } @INPROCEEDINGS{DGPV08a, AUTHOR = {Derbel, Bilel and Gavoille, Cyril and Peleg, David and Viennot, Laurent}, TITLE = {Construction Locale de Sous-Graphes Couvrants Peu Denses}, BOOKTITLE = {$10^{\mbox{\`emes}}$ Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel)}, LOCATION = {Saint-Malo, France}, PAGES = {105-108}, MONTH = may, YEAR = 2008, KEYWORDS = {spanner, distributed} } @INPROCEEDINGS{talk:Gav08, AUTHOR = {Gavoille, Cyril}, TITLE = {On Sparse Spanners}, BOOKTITLE = {ANR Aladdin Meeting}, LOCATION = {La Rochelle, France}, MONTH = may, YEAR = 2008, KEYWORDS = {spanner} } @TECHREPORT{DGPV08, AUTHOR = {Derbel, Bilel and Gavoille, Cyril and Peleg, David and Viennot, Laurent}, TITLE = {On the Locality of Distributed Sparse Spanner Construction}, INSTITUTION= {LaBRI}, ADDRESS = {University of Bordeaux~1, 351, cours de la Lib{\'e}ration, 33405 Talence Cedex, France}, TYPE = {{Research Report}}, NUMBER = {RR-1441-08}, MONTH = feb, YEAR = 2008, KEYWORDS = {spanner, distributed} } @ARTICLE{DG08, AUTHOR = {Derbel, Bilel and Gavoille, Cyril}, TITLE = {Fast Deterministic Distributed Algorithms for Sparse Spanners}, JOURNAL = {Theoretical Computer Science}, VOLUME = 399, NUMBER = {1-2}, PAGES = {83-100}, MONTH = feb, YEAR = 2008, KEYWORDS = {spanner, distributed}, DOI = {10.1016/j.tcs.2008.02.019} } @ARTICLE{GH08, AUTHOR = {Gavoille, Cyril and Hanusse, Nicolas}, TITLE = {On Compact Encoding of Pagenumber $k$ Graphs}, JOURNAL = {Discrete Mathematics \& Theoretical Computer Science}, VOLUME = 10, NUMBER = 3, PAGES = {23-34}, YEAR = 2008, KEYWORDS = {data-structure, pagenumber, coding} } %------ 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 = {Institut 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}, DOI = {10.1007/978-3-540-75142-7_16} } @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, Mamadou 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{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}, DOI = {10.1145/1248377.1248381} } @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}, DOI = {10.1145/1248377.1248379} } @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{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{BGL07, AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Labourel, Arnaud}, TITLE = {Short Labels by Traversal and Jumping}, BOOKTITLE = {$6^{th}$ Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications}, LOCATION = {DIMATIA Center, Charles University, Prague}, EDITOR = {Elsevier}, PUBLISHER = {Electronic Notes in Discrete Mathematics}, VOLUME = 28, MONTH = mar, PAGES = {153-160}, YEAR = 2007, NOTE = {Dedicated to Jarik Ne\v{s}et\v{r}il on the occasion of his 60th birthday}, KEYWORDS = {labeling scheme, planar}, DOI = {10.1016/j.endm.2007.01.022} } @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{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 = {tree-decomposition}, DOI = {10.1016/j.disc.2005.12.060} } %------ 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'adjacence compact 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}, DOI = {10.1007/11821069_3} } @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)}, LOCATION = {Chester, UK}, 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{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{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)}, LOCATION = {Chester, UK}, 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{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}, DOI = {10.1145/1146381.1146411} } @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} } @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}, DOI = {10.1016/j.comnet.2005.09.025} } @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} } @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, KEYWORDS = {small world}, DOI = {10.1007/s00446-005-0137-4} } @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 --------------------------------------------------------- @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{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, KEYWORDS = {data-structure, permutation graph, labeling scheme}, DOI = {10.1007/11602613_111} } @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}, DOI = {10.1007/11602613_106} } @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, KEYWORDS = {compact routing, name-independent, minor}, DOI = {10.1007/11561927_32} } @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\'el\'ecom 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}, DOI = {10.1007/11429647_2} } @INPROCEEDINGS{i:Gav05c, AUTHOR = {Gavoille, Cyril}, TITLE = {{\'E}tiquetage des graphes}, BOOKTITLE = {{\'E}cole Jeunes Chercheurs en Algorithmique et Calcul Formel - \'Ecole th\'ematique 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}, DOI = {10.1016/j.tcs.2004.12.008} } %------ 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{FDGM04a, AUTHOR = {Ferchaud, Fr{\'e}d{\'e}ric and Duong, Vu 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}, VOLUME = 1, PAGES = {2.A.3-1--2.A.3-6}, 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\'ees 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} } @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}, DOI = {10.1007/978-3-540-30186-8_22} } @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{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}, DOI = {10.1145/1007912.1007916} } @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}, DOI = {10.1145/1011767.1011793} } @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{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)}, LOCATION = {Smolenice Castle, Slovakia}, 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, tree-decomposition} } @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}, PAGES = {270-284}, MONTH = jun, YEAR = 2004, KEYWORDS = {coding, planar}, DOI = {10.1007/b104584} } @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 = {tree-decomposition} } @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} } @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, NUMBER = 3, PAGES = {441-456}, MONTH = may, YEAR = 2004, KEYWORDS = {labeling scheme, nca}, DOI = {10.1007/s00224-004-1155-5} } @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} } @TECHREPORT{CGMF04, AUTHOR = {Castanet, Richard and Gavoille, Cyril and Mosbah, Mohamed and Ferchaud, Fr\'ed\'eric}, TITLE = {Utilisation des zones d'absorption pour am\'eliorer la gestion de flux du trafic a\'erien}, INSTITUTION= {LaBRI, Universit\'e Bordeaux~1 - ENSEIRB}, TYPE = {Rapport de contrat (interm\'ediaire)}, NUMBER = {march\'e C/1.291/CE/NB/03/ - EUROCONTROL - ADERA}, MONTH = jan, YEAR = 2004, KEYWORDS = {contract, atfm} } @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, KEYWORDS = {distance labeling}, DOI = {10.1016/j.jalgor.2004.05.002} } %------ 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} } @TECHREPORT{CGMF03, AUTHOR = {Castanet, Richard and Gavoille, Cyril and Mosbah, Mohamed and Ferchaud, Fr\'ed\'eric}, TITLE = {Gestion de flux du traffic a\'erien en intra et inter r\'eseaux~: un mod\`ele de graphes \'evolutifs}, 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, atfm} } @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 = {tree-decomposition} } @ARTICLE{GP03c, AUTHOR = {Gavoille, Cyril and Peleg, David}, TITLE = {Compact and Localized Distributed Data Structures}, JOURNAL = {Distributed Computing}, PUBLISHER = {Springer-Verlag}, VOLUME = 16, NUMBER = {2-3}, PAGES = {111-120}, MONTH = sep, YEAR = 2003, NOTE = {PODC 20-Year Special Issue}, KEYWORDS = {labeling scheme, data-structure}, DOI = {10.1007/s00446-002-0073-5} } @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)}, LOCATION = {Ume\aa, Sweden}, PUBLISHER = {Carleton University Press}, PAGES = {149-164}, MONTH = jun, YEAR = 2003, KEYWORDS = {interval routing, percolation} } @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}, MONTH = apr, YEAR = 2003, KEYWORDS = {interval routing}, DOI = {10.1016/S1570-8667(03)00027-3} } @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} } @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} } @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} } @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{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}, DOI = {10.1007/3-540-36108-1_17} } @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}, DOI = {10.1145/564870.564914} } @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-487}, MONTH = aug, YEAR = 2001, KEYWORDS = {distance labeling}, DOI = {10.1007/3-540-44676-1_40} } @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, NUMBER = 4, PAGES = {217-229}, MONTH = jul, YEAR = 2001, KEYWORDS = {interval routing, broadcast}, DOI = {10.1007/s004460100058} } @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}, DOI = {10.1007/3-540-48224-5_62} } @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{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}, LOCATION = {St-Jean de Luz, France}, 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} } @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} } @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}, DOI = {10.1145/568438.568451} } @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}, DOI = {10.1137/S0097539799351717} } @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} } @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} } %------ 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{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{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}, DOI = {10.1145/343477.343503} } @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}, LOCATION = {L'Aquila, Italy}, 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{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 = {243-249}, YEAR = 2000, KEYWORDS = {interval routing}, DOI = {10.1093/comjnl/43.3.243} } @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} } @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} } %------ 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}, DOI = {10.1137/S0895480197328631} } @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}, LOCATION = {Puerto Vallarta, Mexico}, PAGES = {11-20}, MONTH = aug, YEAR = 1998, KEYWORDS = {compact routing, interval routing}, DOI = {10.1145/277697.277702} } @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}, LOCATION = {Amalfi, Italy}, 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} } @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} } @ARTICLE{FG98a, AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril}, TITLE = {Interval Routing Schemes}, JOURNAL = {Algorithmica}, VOLUME = 21, PAGES = {155-182}, YEAR = 1998, KEYWORDS = {interval routing}, DOI = {10.1007/PL00009211} } %------ 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}, LOCATION = {Ascona, Switzerland}, 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}, MONTH = nov, YEAR = 1996, 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}, MONTH = oct, YEAR = 1996, KEYWORDS = {interval 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}, LOCATION = {Siena, Italy}, PUBLISHER = {Carleton University Press}, PAGES = {88-103}, MONTH = jun, 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}, DOI = {10.1145/237502.237541} } @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}, LOCATION = {Philadelphia, Pennsylvania, USA}, PAGES = {125-133}, YEAR = 1996, MONTH = may, KEYWORDS = {compact routing}, DOI = {10.1145/248052.248075} } @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}, LOCATION = {Ottawa, Ontario, Canada}, PAGES = {223-230}, MONTH = aug, YEAR = 1995, KEYWORDS = {compact routing}, DOI = {10.1145/224964.224989} } @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)}, EDITOR = {Kirousis, Lefteris M. and Kranakis, Evangelos}, LOCATION = {Olympia, Greece}, 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}, LOCATION = {Los Angeles, California, USA}, PAGES = {216-224}, MONTH = aug, YEAR = 1994, KEYWORDS = {interval routing}, DOI = {10.1145/197917.198095} } @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} }