9 Search Results for "Vaxès, Yann"

Document
DOI: 10.4230/LIPIcs.ESA.2025.39
Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.
Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.12
Testing Whether a Subgraph Is Convex or Isometric

Authors: Sergio Cabello

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider the following two algorithmic problems: given a graph G and a subgraph H ⊆ G, decide whether H is an isometric or a geodesically convex subgraph of G. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with n vertices and Θ(n) edges, we cannot expect to solve the problem in O(n^{2-ε}) time for any constant ε > 0. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where G is a plane graph and H is defined by a few cycles in G.
Cite as

Sergio Cabello. Testing Whether a Subgraph Is Convex or Isometric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello:LIPIcs.WADS.2025.12,
  author =	{Cabello, Sergio},
  title =	{{Testing Whether a Subgraph Is Convex or Isometric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.12},
  URN =		{urn:nbn:de:0030-drops-242439},
  doi =		{10.4230/LIPIcs.WADS.2025.12},
  annote =	{Keywords: convex subgraph, isometric subgraph, plane graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.36
Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs

Authors: James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In this paper, we consider the class 𝒞^d of sphere intersection graphs in R^d for d ≥ 2. We show that for each integer t, the class of all graphs in 𝒞^d that exclude K_{t,t} as a subgraph has strongly sublinear separators. We also prove that 𝒞^d has asymptotic dimension at most 2d+2.
Cite as

James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty. Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2025.36,
  author =	{Davies, James and Georgakopoulos, Agelos and Hatzel, Meike and McCarty, Rose},
  title =	{{Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.36},
  URN =		{urn:nbn:de:0030-drops-231881},
  doi =		{10.4230/LIPIcs.SoCG.2025.36},
  annote =	{Keywords: Intersection graphs, strongly sublinear separators, asymptotic dimension}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.17
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Authors: Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}).
Cite as

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2025.17,
  author =	{Bhore, Sujoy and Chan, Timothy M. and Huang, Zhengcheng and Smorodinsky, Shakhar and T\'{o}th, Csaba D.},
  title =	{{Sparse Bounded Hop-Spanners for Geometric Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.17},
  URN =		{urn:nbn:de:0030-drops-231698},
  doi =		{10.4230/LIPIcs.SoCG.2025.17},
  annote =	{Keywords: Geometric Spanners, Geometric Intersection Graphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.9
Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2024.9,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.9},
  URN =		{urn:nbn:de:0030-drops-225452},
  doi =		{10.4230/LIPIcs.OPODIS.2024.9},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.32
Isometric Path Complexity of Graphs

Authors: Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
A set S of isometric paths of a graph G is "v-rooted", where v is a vertex of G, if v is one of the end-vertices of all the isometric paths in S. The isometric path complexity of a graph G, denoted by ipco (G), is the minimum integer k such that there exists a vertex v ∈ V(G) satisfying the following property: the vertices of any isometric path P of G can be covered by k many v-rooted isometric paths. First, we provide an O(n² m)-time algorithm to compute the isometric path complexity of a graph with n vertices and m edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, hyperbolic graphs, (theta, prism, pyramid)-free graphs, and outerstring graphs. Hyperbolic graphs are extensively studied in Metric Graph Theory. The class of (theta, prism, pyramid)-free graphs are extensively studied in Structural Graph Theory, e.g. in the context of the Strong Perfect Graph Theorem. The class of outerstring graphs is studied in Geometric Graph Theory and Computational Geometry. Our results also show that the distance functions of these (structurally) different graph classes are more similar than previously thought. There is a direct algorithmic consequence of having small isometric path complexity. Specifically, using a result of Chakraborty et al. [ISAAC 2022], we show that if the isometric path complexity of a graph G is bounded by a constant k, then there exists a k-factor approximation algorithm for Isometric Path Cover, whose objective is to cover all vertices of a graph with a minimum number of isometric paths.
Cite as

Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès. Isometric Path Complexity of Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2023.32,
  author =	{Chakraborty, Dibyayan and Chalopin, J\'{e}r\'{e}mie and Foucaud, Florent and Vax\`{e}s, Yann},
  title =	{{Isometric Path Complexity of Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-185666},
  doi =		{10.4230/LIPIcs.MFCS.2023.32},
  annote =	{Keywords: Shortest paths, Isometric path complexity, Hyperbolic graphs, Truemper Configurations, Outerstring graphs, Isometric Path Cover}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.31
Sample Compression Schemes for Balls in Graphs

Authors: Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.
Cite as

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.MFCS.2022.31,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Mc Inerney, Fionn and Ratel, S\'{e}bastien and Vax\`{e}s, Yann},
  title =	{{Sample Compression Schemes for Balls in Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.31},
  URN =		{urn:nbn:de:0030-drops-168298},
  doi =		{10.4230/LIPIcs.MFCS.2022.31},
  annote =	{Keywords: Proper Sample Compression Schemes, Balls, Graphs, VC-dimension}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.10
Medians in Median Graphs and Their Cube Complexes in Linear Time

Authors: Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the 𝓁₁-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of G satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of G are also adjacent.
Cite as

Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in Median Graphs and Their Cube Complexes in Linear Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beneteau_et_al:LIPIcs.ICALP.2020.10,
  author =	{B\'{e}n\'{e}teau, Laurine and Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Vax\`{e}s, Yann},
  title =	{{Medians in Median Graphs and Their Cube Complexes in Linear Time}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.10},
  URN =		{urn:nbn:de:0030-drops-124171},
  doi =		{10.4230/LIPIcs.ICALP.2020.10},
  annote =	{Keywords: Median Graph, CAT(0) Cube Complex, Median Problem, Linear Time Algorithm, LexBFS}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.22
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Authors: Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.
Cite as

Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.SoCG.2018.22,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Dragan, Feodor F. and Ducoffe, Guillaume and Mohammed, Abdulhakeem and Vax\`{e}s, Yann},
  title =	{{Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.22},
  URN =		{urn:nbn:de:0030-drops-87356},
  doi =		{10.4230/LIPIcs.SoCG.2018.22},
  annote =	{Keywords: Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms}
}
  • Refine by Type
  • 9 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2023
  • 1 2022
  • 1 2020
  • 1 2018

  • Refine by Author
  • 4 Chalopin, Jérémie
  • 4 Vaxès, Yann
  • 3 Chepoi, Victor
  • 1 Bhore, Sujoy
  • 1 Bramas, Quentin
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Computing methodologies → Mobile agents
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Graphs
  • 1 Approximation algorithms
  • 1 Balls
  • 1 CAT(0) Cube Complex
  • 1 Distributed Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact