Skip to Main content Skip to Navigation

hal-02101800v1  Reports
Cyril GavoilleEric Guevremont. Worst Case Bounds for Shortest Path Interval Routing
[Research Report] LIP RR-1995-02, Laboratoire de l'informatique du parallélisme. 1995, 2+23p
hal-02101881v1  Reports
Pierre FraigniaudCyril Gavoille. Local memory requirement of universal routing schemes.
[Research Report] LIP RR-1996-01, Laboratoire de l'informatique du parallélisme. 1996, 2+8p
inria-00098892v1  Conference papers
Johanne CohenPierre FraigniaudCyril Gavoille. Recognizing Bipartite Incident-Graphs of Circulant Digraphs
International Workshop on Graph Theoretic Concepts in Computer Science - WG'99, 1999, Ascona, Switzerland, pp.215-227
inria-00100969v1  Journal articles
Johanne CohenPierre FraigniaudCyril Gavoille. Recognizing Knödel graphs
Discrete Mathematics, Elsevier, 2002, pp.41-62
hal-00307381v1  Journal articles
Cyril GavoilleDavid PelegStéphane PérennesRan Raz. Distance Labeling in Graphs
Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 2004, 53, pp.85-112
hal-00353638v1  Conference papers
Olivier LyCyril Gavoille. Distance Labeling in Hyperbolic Graphs
16th Annual International Symposium on Algorithms and Computation, ISAAC, 2005, France. pp.1071-1081
hal-00420405v1  Conference papers
Ittai AbrahamCyril GavoilleDahlia Malkhi. On Space-Stretch Trade-Offs: Upper Bounds
Symposium on Parallel Algorithms and Architectures (SPAA), 2006, Cambridge, Massachusetts, United States. pp.207-216, ⟨10.1145/1148109.1148144⟩
hal-00307800v1  Journal articles
Yon DourisboureCyril Gavoille. Tree-Decompositions with Bags of Small Diameter
Discrete Mathematics, Elsevier, 2007, 307 (16), pp.2008-2029. ⟨10.1016/j.disc.2005.12.060⟩
hal-00371393v1  Journal articles
Tamar EilamCyril GavoilleDavid Peleg. Average Stretch Analysis of Compact Routing Schemes
Discrete Applied Mathematics, Elsevier, 2007, 155, pp.598-610. ⟨10.1016/j.dam.2006.09.010⟩
hal-00155186v1  Conference papers
Pierre FraigniaudCyril GavoilleAdrian KosowskiEmmanuelle LebharZvi Lotker. Universal augmentation schemes for network navigability: overcoming the $\sqrt n$-barrier
nineteenth annual ACM symposium on parallelism and architectures, 2007, San Diego, California, United States. pp.1-7
hal-00369657v1  Conference papers
Cyril GavoilleNicolas BonichonArnaud Labourel. Short Labels by Traversal and Jumping
6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, mars 2007, Mar 2007, Prague, Czech Republic. pp.153-160, ⟨10.1016/j.endm.2007.01.022⟩
hal-00371401v1  Conference papers
Ittai AbrahamCyril GavoilleDahlia MalkhiUdi Wieder. Strong-Diameter Decompositions of Minor Free Graphs
19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, Californie, Etats-Unis, 2007, Jun 2007, San Diego, United States. pp.16-24, ⟨10.1145/1248377.1248381⟩
hal-00369644v1  Conference papers
Cyril GavoilleArnaud Labourel. Brief Announcement: On Local Representation of Distances in Trees
26th Annual ACM Symposium on Principles of Distributed Computing (PODC), août 2007, Portland, WA, Etats-Unis, Aug 2007, Portland, United States. pp.246-247, ⟨10.1145/1281100.1281169⟩
hal-00371154v1  Conference papers
Cyril Gavoille. Localized Data Structures (Keynote Talk)
2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), PODC, Portland, Oregon, Etats-Unis, août 2007, Aug 2007, Portland, United States
hal-00369662v1  Conference papers
Bruno CourcelleCyril GavoilleMamadou Moustapha KantéAndrew Twigg. Forbidden-Set Labeling on Graphs
2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), Portland, Etats-Unis, Aug 2007, Portland, United States
hal-00371381v1  Conference papers
Cyril GavoilleBilel DerbelDavid Peleg. Deterministic Distributed Construction of Linear Stretch Spanners in Polygarithmic Time
21rst International Symposium on Distributed Computing (DISC), Lemesos, Chypre, 2007, Sep 2007, Lemesos, Cyprus. pp.179-192, ⟨10.1007/978-3-540-75142-7_16⟩
hal-00369676v1  Journal articles
Yon DourisboureFeodor DraganCyril GavoilleChenyu Yan. Spanners for Bounded Tree-Length Graphs
Theoretical Computer Science, Elsevier, 2007, 383 (1), pp.34-44. ⟨10.1016/j.tcs.2007.03.058⟩
hal-00369655v1  Conference papers
Cyril GavoilleRalf KlasingAdrian KosowskiAlfredo Navarra. Brief Announcement: On the Complexity of Distributed Greedy Coloring
21rst International Symposium on Distributed Computing (DISC), septembre 2007, Lemesos, Chypre, Sep 2007, Lemesos, Cyprus. pp.482-484
hal-00369646v1  Conference papers
Cyril GavoilleArnaud Labourel. Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
15th Annual European Symposium on Algorithms (ESA), octobre 2007, Eilat, Israël, Oct 2007, Eilat, Israel. pp.582-593
hal-00369624v1  Conference papers
Cyril GavoilleArnaud Labourel. Schéma relationnel distribué pour les arbres
9èmes Journées Graphes et Algorithmes, Paris, novembre 2007, Nov 2007, Paris, France. pp.19
hal-00369633v1  Conference papers
Cyril GavoilleArnaud Labourel. Distributed Relationship Schemes for Trees
18th Annual International Symposium on Algorithms and Computation (ISAAC), décembre 2007, Sendai, Japon, Dec 2007, Sendai, Japan. pp.728-738, ⟨10.1007/978-3-540-77120-3_63⟩
hal-00402218v1  Journal articles
Cyril GavoilleNicolas Hanusse. On Compact Encoding of Pagenumber $k$ Graphs
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.23-34
hal-00368037v1  Journal articles
Cyril GavoilleBilel Derbel. Fast Deterministic Distributed Algorithms for Sparse Spanners
Theoretical Computer Science, Elsevier, 2008, 399 (1-2), pp.83-100
hal-00368035v1  Conference papers
Cyril GavoilleBilel DerbelDavid PelegLaurent Viennot. Construction locale de sous-graphes couvrants peu denses
10ièmes Rencontres francophones sur les aspects algorithmiques des télécommunications (AlgoTel), Saint-Malo, France, 2008, May 2008, France. pp.105-108
hal-00367998v1  Conference papers
Cyril GavoillePierre Fraigniaud. Polylogarithmic Network Navigability Using Compact Metrics with Small Stretch
20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Munich, Allemagne, juin 2008, Jun 2008, Munich, Germany. pp.62-69, ⟨10.1145/1378533.1378542⟩
hal-00368010v1  Journal articles
Cyril GavoilleIttai AbrahamDahlia MalkhiNoam NisanMikkel Thorup. Compact Name-Independent Routing with Minimum Stretch
ACM Transactions on Algorithms, Association for Computing Machinery, 2008, 3 (4), pp.Article 37. ⟨10.1145/1367064.1367077⟩
hal-00366618v1  Journal articles
Cyril GavoilleChristophe Paul. Optimal Distance Labeling for Interval Graphs and Related Graphs Families
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (3), pp.1239-1258. ⟨10.1137/050635006⟩
hal-00343001v1  Conference papers
Cyril GavoilleBilel DerbelDavid PelegLaurent Viennot. On the Locality of Distributed Sparse Spanner Construction
27th Annual ACM Symposium on Principles of Distributed Computing (PODC), Aug 2008, Toronto, Canada. pp.273-282, ⟨10.1145/1400751.1400788⟩