Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs

Autor: Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, Andrzej Pelc

Publikováno v: ACM Transactions on Algorithms. 19:1-32

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::d09291e9d329ad67ddfda1a7dca97c2a
https://doi.org/10.1145/3588437

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

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

Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots

Autor: Maxime Godon, Evangelos Kranakis, Arnaud Labourel, Euripides Markou, Jurek Czyzowicz

Publikováno v: SOFSEM 2018: Theory and Practice of Computer Science ISBN: 9783319731162
SOFSEM
44th International Conference on Current Trends in Theory and Practice of Computer Science
44th International Conference on Current Trends in Theory and Practice of Computer Science, Jan 2018, Krems an der Donau, France. pp.381-395

A graph environment must be explored by a collection of mobile robots. Some of the robots, a priori unknown, may turn out to be unreliable. The graph is weighted and each node is assigned a deadline. The exploration is successful if each node of the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::10ce594060f51dc553fa6d676f75c7ed
https://doi.org/10.1007/978-3-319-73117-9_27

Coloring Non-Crossing Strings

Autor: Arnaud Labourel, Daniel Gonçalves, Louis Esperet

Publikováno v: The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, 2016, 23 (4), pp.4.4. ⟨10.37236/5710⟩
The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (4), pp.4.4

For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$, define $\chi(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cc68b38381eb0ace6a697d4b7eae584f
https://doi.org/10.37236/5710