Cyril Gavoille

According to our database, Cyril Gavoille authored at least 117 papers between 1994 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Freeze-Tag in L₁ has Wake-up Time Five.

Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, Nicolas Hanusse

CoRR, 2024

2023

Minor-Universal Graph for Graphs on Surfaces.

Cyril Gavoille, Claire Hilaire

CoRR, 2023

2022

Shorter Labeling Schemes for Planar Graphs.

Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk

SIAM J. Discret. Math., September, 2022

2021

Isometric Universal Graphs.

Louis Esperet, Cyril Gavoille, Carla Groenland

SIAM J. Discret. Math., 2021

Adjacency Labelling for Planar Graphs (and Beyond).

Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin

J. ACM, 2021

2021 Edsger W. Dijkstra Prize in Distributed Computing.

Keren Censor-Hillel, Pierre Fraigniaud, Cyril Gavoille, Seth Gilbert, Andrzej Pelc, David Peleg

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

On the Treewidth of Planar Minor Free Graphs.

Youssou Dieng, Cyril Gavoille

Proceedings of the Innovations and Interdisciplinary Solutions for Underserved Areas, 2020

2019

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.

Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar

SIAM J. Comput., 2019

Localisation-Resistant Random Words with Small Alphabets.

Cyril Gavoille, Ghazal Kachigar, Gilles Zémor

Proceedings of the Combinatorics on Words - 12th International Conference, 2019

2018

A fast network-decomposition algorithm and its applications to constant-time distributed computation.

Leonid Barenboim, Michael Elkin, Cyril Gavoille

Theor. Comput. Sci., 2018

2017

Towards plane spanners of degree 3.

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, Michiel H. M. Smid

J. Comput. Geom., 2017

2016

Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension.

Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg

ACM Trans. Algorithms, 2016

Simpler, faster and shorter labels for distances in graphs.

Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Tight stretch factors for L₁- and L_∞-Delaunay triangulations.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic

Comput. Geom., 2015

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract).

Leonid Barenboim, Michael Elkin, Cyril Gavoille

Proceedings of the Structural Information and Communication Complexity, 2015

Brief Announcement: Routing the Internet with Very Few Entries.

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2013

On the Communication Complexity of Distributed Name-Independent Routing Schemes.

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, David Ilcinkas

Proceedings of the Distributed Computing - 27th International Symposium, 2013

2012

The Stretch Factor of L₁- and L_∞-Delaunay Triangulations

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic

CoRR, 2012

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.

Ittai Abraham, Shiri Chechik, Cyril Gavoille

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic

Proceedings of the Algorithms - ESA 2012, 2012

2011

Routage compact optimal dans les <i>(k, r)</i>-constellations.

Youssou Dieng, Cyril Gavoille

Tech. Sci. Informatiques, 2011

Compact labelings for efficient first-order model-checking.

Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté

J. Comb. Optim., 2011

On Approximate Distance Labels and Routing Schemes with Affine Stretch.

Ittai Abraham, Cyril Gavoille

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Sparse spanners vs. compact routing.

Cyril Gavoille, Christian Sommer

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners.

Cyril Gavoille, Quentin Godfroy, Laurent Viennot

Proceedings of the Principles of Distributed Systems - 15th International Conference, 2011

An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse

Proceedings of the Towards an Information Theory of Complex Networks, 2011

2010

Foreword.

Cyril Gavoille, Boaz Patt-Shamir, Christian Scheideler

Theory Comput. Syst., 2010

Strong-Diameter Decompositions of Minor Free Graphs.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Udi Wieder

Theory Comput. Syst., 2010

Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, David Ilcinkas

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Multipath Spanners.

Cyril Gavoille, Quentin Godfroy, Laurent Viennot

Proceedings of the Structural Information and Communication Complexity, 2010

Plane Spanners of Maximum Degree Six.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Path Separability of Graphs.

Emilie Diot, Cyril Gavoille

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009

Universal augmentation schemes for network navigability.

Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, Zvi Lotker

Theor. Comput. Sci., 2009

On the complexity of distributed graph coloring with local minimality constraints.

Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz Kuszner, Alfredo Navarra

Networks, 2009

On the Path Separability of Planar Graphs.

Emilie Diot, Cyril Gavoille

Electron. Notes Discret. Math., 2009

On the Tree-Width of Planar Graphs.

Youssou Dieng, Cyril Gavoille

Electron. Notes Discret. Math., 2009

Localized and compact data-structure for comparability graphs.

Fabrice Bazzaro, Cyril Gavoille

Discret. Math., 2009

Distributed computing with advice: information sensitivity of graph coloring.

Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, Andrzej Pelc

Distributed Comput., 2009

What Can Be Observed Locally?

Cyril Gavoille, Adrian Kosowski, Marcin Markiewicz

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Local Computation of Nearly Additive Spanners.

Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

2008

Fast deterministic distributed algorithms for sparse spanners.

Bilel Derbel, Cyril Gavoille

Theor. Comput. Sci., 2008

Compact name-independent routing with minimum stretch.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup

ACM Trans. Algorithms, 2008

Optimal Distance Labeling for Interval Graphs and Related Graph Families.

Cyril Gavoille, Christophe Paul

SIAM J. Discret. Math., 2008

Connectivity check in 3-connected planar graphs with obstacles.

Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, Andrew Twigg

Electron. Notes Discret. Math., 2008

On Compact Encoding of Pagenumber.

Cyril Gavoille, Nicolas Hanusse

Discret. Math. Theor. Comput. Sci., 2008

Polylogarithmic network navigability using compact metrics with small stretch.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

On the locality of distributed sparse spanner construction.

Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Efficient First-Order Model-Checking Using Short Labels.

Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté

Proceedings of the Frontiers in Algorithmics, Second Annual International Workshop, 2008

2007

Spanners for bounded tree-length graphs.

Yon Dourisboure, Feodor F. Dragan, Cyril Gavoille, Chenyu Yan

Theor. Comput. Sci., 2007

Short Labels by Traversal and Jumping.

Nicolas Bonichon, Cyril Gavoille, Arnaud Labourel

Electron. Notes Discret. Math., 2007

Tree-decompositions with bags of small diameter.

Yon Dourisboure, Cyril Gavoille

Discret. Math., 2007

Average stretch analysis of compact routing schemes.

Tamar Eilam, Cyril Gavoille, David Peleg

Discret. Appl. Math., 2007

On the Complexity of Distributed Greedy Coloring.

Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Alfredo Navarra

Proceedings of the Distributed Computing, 21st International Symposium, 2007

Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time.

Bilel Derbel, Cyril Gavoille, David Peleg

Proceedings of the Distributed Computing, 21st International Symposium, 2007

Universal augmentation schemes for network navigability: overcoming the sqrt(n)-barrier.

Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, Zvi Lotker

Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

On local representation of distances in trees.

Cyril Gavoille, Arnaud Labourel

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Distributed Relationship Schemes for Trees.

Cyril Gavoille, Arnaud Labourel

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.

Cyril Gavoille, Arnaud Labourel

Proceedings of the Algorithms, 2007

2006

Planar Graphs, via Well-Orderly Maps and Trees.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer

Graphs Comb., 2006

Eclecticism shrinks even small worlds.

Pierre Fraigniaud, Cyril Gavoille, Christophe Paul

Distributed Comput., 2006

Header-size lower bounds for end-to-end communication in memoryless networks.

Pierre Fraigniaud, Cyril Gavoille

Comput. Networks, 2006

On space-stretch trade-offs: upper bounds.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

On space-stretch trade-offs: lower bounds.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Object location using path separators.

Ittai Abraham, Cyril Gavoille

Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Distributed Data Structures: A Survey on Informative Labeling Schemes.

Cyril Gavoille

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Routing in Networks with Low Doubling Dimension.

Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, Dahlia Malkhi

Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 2006

2005

Interval routing in reliability networks.

Cyril Gavoille, Martin Nehéz

Theor. Comput. Sci., 2005

Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse

J. Graph Algorithms Appl., 2005

Edge Partition of Toroidal Graphs into Forests in Linear Time.

Nicolas Bonichon, Cyril Gavoille, Arnaud Labourel

Electron. Notes Discret. Math., 2005

Distance Labeling for Permutation Graphs.

Fabrice Bazzaro, Cyril Gavoille

Electron. Notes Discret. Math., 2005

Compact Routing for Graphs Excluding a Fixed Minor.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi

Proceedings of the Distributed Computing, 19th International Conference, 2005

Distributed Data Structures: A Survey.

Cyril Gavoille

Proceedings of the Structural Information and Communication Complexity, 2005

Distance Labeling in Hyperbolic Graphs.

Cyril Gavoille, Olivier Ly

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment.

Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe

Theory Comput. Syst., 2004

Distance labeling in graphs.

Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz

J. Algorithms, 2004

Routing with Improved Communication-Space Trade-Off.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi

Proceedings of the Distributed Computing, 18th International Conference, 2004

Sparse Additive Spanners for Bounded Tree-Length Graphs.

Yon Dourisboure, Cyril Gavoille

Proceedings of the Structural Information and Communication Complexity, 2004

2003

The compactness of adaptive routing tables.

Cyril Gavoille, Akka Zemmari

J. Discrete Algorithms, 2003

Compact routing schemes with low stretch factor.

Tamar Eilam, Cyril Gavoille, David Peleg

J. Algorithms, 2003

Distance labeling scheme and split decomposition.

Cyril Gavoille, Christophe Paul

Discret. Math., 2003

Compact and localized distributed data structures.

Cyril Gavoille, David Peleg

Distributed Comput., 2003

Lower Bounds for Oblivious Single-Packet End-to-End Communication.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Distributed Computing, 17th International Conference, 2003

An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation.

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Optimal Distance Labeling for Interval and Circular-Arc Graphs.

Cyril Gavoille, Christophe Paul

Proceedings of the Algorithms, 2003

2002

Recognizing Knödel graphs.

Johanne Cohen, Pierre Fraigniaud, Cyril Gavoille

Discret. Math., 2002

Improved Compact Routing Scheme for Chordal Graphs.

Yon Dourisboure, Cyril Gavoille

Proceedings of the Distributed Computing, 16th International Conference, 2002

A Space Lower Bound for Routing in Trees.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Nearest common ancestors: a survey and a new distributed algorithm.

Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe

Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2002

2001

Routing in distributed networks: overview and open problems.

Cyril Gavoille

SIGACT News, 2001

The Compactness of Interval Routing for Almost All Graphs.

Cyril Gavoille, David Peleg

SIAM J. Comput., 2001

Space-Efficiency for Routing Schemes of Stretch Factor Three.

Cyril Gavoille, Marc Gengler

J. Parallel Distributed Comput., 2001

Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs.

Cyril Gavoille, Christophe Paul

Electron. Notes Discret. Math., 2001

Interval routing schemes allow broadcasting with linear message-complexity.

Pierre Fraigniaud, Cyril Gavoille, Bernard Mans

Distributed Comput., 2001

Small k-Dominating Sets in Planar Graphs with Applications.

Cyril Gavoille, David Peleg, André Raspaud, Éric Sopena

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Routing in Trees.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Approximate Distance Labeling Schemes.

Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, David Peleg

Proceedings of the Algorithms, 2001

2000

A survey on interval routing.

Cyril Gavoille

Theor. Comput. Sci., 2000

Approximate Distance Labeling Schemes.

Cyril Gavoille, Christophe Paul

Electron. Notes Discret. Math., 2000

On the Dilation of Interval Routing.

Cyril Gavoille

Comput. J., 2000

Interval routing schemes allow broadcasting with linear message-complexity (extended abstract).

Pierre Fraigniaud, Cyril Gavoille, Bernard Mans

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

On Recognizing Cayley Graphs.

Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, John Michael Robson

Proceedings of the Algorithms, 2000

1999

The Compactness of Interval Routing.

Cyril Gavoille, David Peleg

SIAM J. Discret. Math., 1999

Recognizing Bipartite Incident-Graphs of Circulant Digraphs.

Johanne Cohen, Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Compact Routing Tables for Graphs of Bounded Genus.

Cyril Gavoille, Nicolas Hanusse

Proceedings of the Automata, 1999

1998

Worst Case Bounds for Shortest Path Interval Routing.

Cyril Gavoille, Eric Guévremont

J. Algorithms, 1998

Interval Routing Schemes.

Pierre Fraigniaud, Cyril Gavoille

Algorithmica, 1998

A Theoretical Model for Routing Complexity.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the SIROCCO'98, 1998

Compact Routing Schemes with Low Stretch Factor (Extended Abstract).

Tamar Eilam, Cyril Gavoille, David Peleg

Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

1997

Universal Routing Schemes.

Pierre Fraigniaud, Cyril Gavoille

Distributed Comput., 1997

An Omega(n2)-Lower Bound for Space-Efficiency of Routing Schemes of Stretch Factor Three.

Cyril Gavoille, Marc Gengler

Proceedings of the SIROCCO'97, 1997

1996

Local Memory Requirement of Universal Routing Schemes.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Lower Bounds for Shortest Path Interval Routing.

Cyril Gavoille, Stephane Perennes

Proceedings of the SIROCCO'96, 1996

Memory Requirements for Routing in Distributed Networks (Extended Abstract).

Cyril Gavoille, Stephane Perennes

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

1995

On the Compactness of Bounded Degree Graphs for Shortest Path Interval Routing.

Cyril Gavoille, Eric Guévremont

Proceedings of the Structure, Information and Communication Complexity, 1995

Memory Requirement for Universal Routing Schemes.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

1994

A Characterization of Networks Supporting Linear Interval Routing.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

Optimal Interval Routing.

Pierre Fraigniaud, Cyril Gavoille

Proceedings of the Parallel Processing: CONPAR 94, 1994