Graphs with convex balls

Autor: Jérémie Chalopin, Victor Chepoi, Ugo Giocanti

In this paper, we investigate the graphs in which all balls are convex and the groups acting on them geometrically (which we call CB-graphs and CB-groups).These graphs have been introduced andcharacterized by Soltan and Chepoi (1983) and Farber and J

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::82a7448bb83c862ed16ac4816ff71513
http://arxiv.org/abs/2201.01599

Distance labeling schemes for K4-free bridged graphs

Autor: Sébastien Ratel, Victor Chepoi, Arnaud Labourel

Publikováno v: Structural Information and Communication Complexity
International Colloquium on Structural Information and Communication ComplexitySIROCCO 2020: Structural Information and Communication Complexity pp 310-327
SIROCCO 2020: Structural Information and Communication Complexity
SIROCCO 2020: Structural Information and Communication Complexity, 2020, Padeborn, Germany. pp.310-327, ⟨10.1007/978-3-030-54921-3_18⟩
Information and Computation
Information and Computation, In press, ⟨10.1016/j.ic.2022.104959⟩
Structural Information and Communication Complexity ISBN: 9783030549206
SIROCCO
HAL

$k$-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the $k$-approximation of the distance between any two vertices $u$ and $v$ can be determined efficiently by merely inspectin

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a34bca87464d80207bc5d52446b05998
https://doi.org/10.1016/j.ic.2022.104959

Two-dimensional partial cubes

Autor: Victor Chepoi, Kolja Knauer, Manon Philibert

Publikováno v: The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, 2020, 27 (3), pp.P3.29. ⟨10.37236/8934⟩
The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (3), pp.P3.29
HAL

We investigate the structure of two-dimensional partial cubes, i.e., of isometric subgraphs of hypercubes whose vertex set defines a set family of VC-dimension at most 2. Equivalently, those are the partial cubes which are not contractible to the 3-c

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5c13ce6f3886d510f07b68d834c0a678
https://hal.science/hal-02268768

Distance and routing labeling schemes for cube-free median graphs

Autor: Victor Chepoi, Sébastien Ratel, Arnaud Labourel

Publikováno v: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Aachen, Germany. pp.15:1--15:14, ⟨10.4230/LIPIcs.MFCS.2019.15⟩
Algorithmica
Algorithmica, Springer Verlag, 2021, 83 (1), pp.252-296. ⟨10.1007/s00453-020-00756-w⟩
HAL
Algorithmica, 2021, 83 (1), pp.252-296. ⟨10.1007/s00453-020-00756-w⟩
Algorithmica, Springer Verlag, 2021, 83, pp.252-296

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices $u$ and $v$ can be determined efficiently by merely inspecting the labels of $u$ and $v$, without usin

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0bf114ea2d0e7ccb2590139cf2953e78
https://hal.archives-ouvertes.fr/hal-02268771

Medians in median graphs and their cube complexes in linear time

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

Publikováno v: ICALP 2020 47th International Colloquium on Automata, Languages, and Programming
ICALP 2020 47th International Colloquium on Automata, Languages, and Programming, 2020, Saarbrücken, Germany. pp.10:1--10:17, ⟨10.4230/LIPIcs.ICALP.2020.10⟩
Journal of Computer and System Sciences
Journal of Computer and System Sciences, 2022, 126, pp.80-105. ⟨10.1016/j.jcss.2022.01.001⟩

International audience; 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 gra

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f62723a6f1c620a56703ba551012802