Cyril Gavoille

According to our database1, Cyril Gavoille authored at least 108 papers between 1994 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2018
A fast network-decomposition algorithm and its applications to constant-time distributed computation.
Theor. Comput. Sci., 2018

2016
Simpler, faster and shorter labels for distances in graphs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Towards Plane Spanners of Degree 3.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015
Tight stretch factors for L1- and L-Delaunay triangulations.
Comput. Geom., 2015

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract).
Proceedings of the Structural Information and Communication Complexity, 2015

Brief Announcement: Routing the Internet with Very Few Entries.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2014
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs.
Proceedings of the Symposium on Theory of Computing, 2014

2013
On the Communication Complexity of Distributed Name-Independent Routing Schemes.
Proceedings of the Distributed Computing - 27th International Symposium, 2013

2012
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Routage compact optimal dans les (k, r)-constellations.
Technique et Science Informatiques, 2011

Compact labelings for efficient first-order model-checking.
J. Comb. Optim., 2011

On Approximate Distance Labels and Routing Schemes with Affine Stretch.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

Sparse spanners vs. compact routing.
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.
Proceedings of the Principles of Distributed Systems - 15th International Conference, 2011

An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps.
Proceedings of the Towards an Information Theory of Complex Networks, 2011

2010
Foreword.
Theory Comput. Syst., 2010

Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Multipath Spanners.
Proceedings of the Structural Information and Communication Complexity, 2010

Forbidden-set distance labels for graphs of bounded doubling dimension.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Plane Spanners of Maximum Degree Six.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Path Separability of Graphs.
Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009
Universal augmentation schemes for network navigability.
Theor. Comput. Sci., 2009

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

On the Path Separability of Planar Graphs.
Electronic Notes in Discrete Mathematics, 2009

On the Tree-Width of Planar Graphs.
Electronic Notes in Discrete Mathematics, 2009

What Can Be Observed Locally?
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Local Computation of Nearly Additive Spanners.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

2008
Optimal Distance Labeling for Interval Graphs and Related Graph Families.
SIAM J. Discrete Math., 2008

Connectivity check in 3-connected planar graphs with obstacles.
Electronic Notes in Discrete Mathematics, 2008

On Compact Encoding of Pagenumber.
Discrete Mathematics & Theoretical Computer Science, 2008

Polylogarithmic network navigability using compact metrics with small stretch.
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.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Efficient First-Order Model-Checking Using Short Labels.
Proceedings of the Frontiers in Algorithmics, Second Annual International Workshop, 2008

2007
Spanners for bounded tree-length graphs.
Theor. Comput. Sci., 2007

Tree-decompositions with bags of small diameter.
Discrete Mathematics, 2007

Average stretch analysis of compact routing schemes.
Discrete Applied Mathematics, 2007

On the Complexity of Distributed Greedy Coloring.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Universal augmentation schemes for network navigability: overcoming the sqrt(n)-barrier.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Strong-diameter decompositions of minor free graphs.
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.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Distributed Relationship Schemes for Trees.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Distributed Computing with Advice: Information Sensitivity of Graph Coloring.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.
Proceedings of the Algorithms, 2007

2006
Header-size lower bounds for end-to-end communication in memoryless networks.
Computer Networks, 2006

On space-stretch trade-offs: upper bounds.
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.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Fast Deterministic Distributed Algorithms for Sparse Spanners.
Proceedings of the Structural Information and Communication Complexity, 2006

Short Labels by Traversal and Jumping.
Proceedings of the Structural Information and Communication Complexity, 2006

Object location using path separators.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Distributed Data Structures: A Survey on Informative Labeling Schemes.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Routing in Networks with Low Doubling Dimension.
Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 2006

2005
Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation.
J. Graph Algorithms Appl., 2005

Edge Partition of Toroidal Graphs into Forests in Linear Time.
Electronic Notes in Discrete Mathematics, 2005

Distance Labeling for Permutation Graphs.
Electronic Notes in Discrete Mathematics, 2005

Compact Routing for Graphs Excluding a Fixed Minor.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Distributed Data Structures: A Survey.
Proceedings of the Structural Information and Communication Complexity, 2005

Distance Labeling in Hyperbolic Graphs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Localized and Compact Data-Structure for Comparability Graphs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004
Planar Graphs, via Well-Orderly Maps and Trees.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Routing with Improved Communication-Space Trade-Off.
Proceedings of the Distributed Computing, 18th International Conference, 2004

Compact name-independent routing with minimum stretch.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Sparse Additive Spanners for Bounded Tree-Length Graphs.
Proceedings of the Structural Information and Communication Complexity, 2004

Eclecticism shrinks even small worlds.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

2003
Compact routing schemes with low stretch factor.
J. Algorithms, 2003

Distance labeling scheme and split decomposition.
Discrete Mathematics, 2003

Compact and localized distributed data structures.
Distributed Computing, 2003

Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Lower Bounds for Oblivious Single-Packet End-to-End Communication.
Proceedings of the Distributed Computing, 17th International Conference, 2003

An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Interval Routing in Reliability Networks.
Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

Optimal Distance Labeling for Interval and Circular-Arc Graphs.
Proceedings of the Algorithms, 2003

2002
Recognizing Knödel graphs.
Discrete Mathematics, 2002

Improved Compact Routing Scheme for Chordal Graphs.
Proceedings of the Distributed Computing, 16th International Conference, 2002

A Space Lower Bound for Routing in Trees.
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.
Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2002

2001
Routing in distributed networks: overview and open problems.
SIGACT News, 2001

Space-Efficiency for Routing Schemes of Stretch Factor Three.
J. Parallel Distrib. Comput., 2001

Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs.
Electronic Notes in Discrete Mathematics, 2001

Interval routing schemes allow broadcasting with linear message-complexity.
Distributed Computing, 2001

Small k-Dominating Sets in Planar Graphs with Applications.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Distance labeling in graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Routing in Trees.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Approximate Distance Labeling Schemes.
Proceedings of the Algorithms, 2001

2000
A survey on interval routing.
Theor. Comput. Sci., 2000

Approximate Distance Labeling Schemes.
Electronic Notes in Discrete Mathematics, 2000

The compactness of adaptive routing tables.
Proceedings of the SIROCCO 7, 2000

Interval routing schemes allow broadcasting with linear message-complexity (extended abstract).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

On Recognizing Cayley Graphs.
Proceedings of the Algorithms, 2000

1999
The Compactness of Interval Routing.
SIAM J. Discrete Math., 1999

Recognizing Bipartite Incident-Graphs of Circulant Digraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Compact Routing Tables for Graphs of Bounded Genus.
Proceedings of the Automata, 1999

1998
Worst Case Bounds for Shortest Path Interval Routing.
J. Algorithms, 1998

Interval Routing Schemes.
Algorithmica, 1998

The Compactness of Interval Routing for Almost All Graphs.
Proceedings of the Distributed Computing, 12th International Symposium, 1998

A Theoretical Model for Routing Complexity.
Proceedings of the SIROCCO'98, 1998

Compact Routing Schemes with Low Stretch Factor (Extended Abstract).
Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

1997
Universal Routing Schemes.
Distributed Computing, 1997

An Omega(n2)-Lower Bound for Space-Efficiency of Routing Schemes of Stretch Factor Three.
Proceedings of the SIROCCO'97, 1997

On the Dilation of Interval Routing.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996
Local Memory Requirement of Universal Routing Schemes.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Lower Bounds for Shortest Path Interval Routing.
Proceedings of the SIROCCO'96, 1996

Memory Requirements for Routing in Distributed Networks (Extended Abstract).
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.
Proceedings of the Structure, Information and Communication Complexity, 1995

Memory Requirement for Universal Routing Schemes.
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

1994
A Characterization of Networks Supporting Linear Interval Routing.
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

Optimal Interval Routing.
Proceedings of the Parallel Processing: CONPAR 94, 1994


  Loading...