Search Results

Documents authored by Labourel, Arnaud

Document
DOI: 10.4230/LIPIcs.SAND.2022.9
Robustness of Distances and Diameter in a Fragile Network

Authors: Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
A property of a graph G is robust if it remains unchanged in all connected spanning subgraphs of G. This form of robustness is motivated by networking contexts where some links eventually fail permanently, and the network keeps being used so long as it is connected. It is then natural to ask how certain properties of the network may be impacted as the network deteriorates. In this paper, we focus on two particular properties, which are the diameter, and pairwise distances among nodes. Surprisingly, the complexities of deciding whether these properties are robust are quite different: deciding the robustness of the diameter is coNP-complete, whereas deciding the robustness of the distance between two given nodes has a linear time complexity. This is counterintuitive, because the diameter consists of the maximum distance over all pairs of nodes, thus one may expect that the robustness of the diameter reduces to testing the robustness of pairwise distances. On the technical side, the difficulty of the diameter is established through a reduction from hamiltonian paths. The linear time algorithm for deciding robustness of the distance relies on a new characterization of two-terminal series-parallel graphs (TTSPs) in terms of excluded rooted minor, which may be of independent interest.
Cite as

Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel. Robustness of Distances and Diameter in a Fragile Network. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.SAND.2022.9,
  author =	{Casteigts, Arnaud and Corsini, Timoth\'{e}e and Hocquard, Herv\'{e} and Labourel, Arnaud},
  title =	{{Robustness of Distances and Diameter in a Fragile Network}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.9},
  URN =		{urn:nbn:de:0030-drops-159514},
  doi =		{10.4230/LIPIcs.SAND.2022.9},
  annote =	{Keywords: Dynamic networks, Longest path, Series-parallel graphs, Rooted minors}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.36
Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

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

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A mobile agent navigating along edges of a simple connected 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 knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most {⌊ B⌋} edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d), and then show how to modify this algorithm to work in the model from [Baruch Awerbuch et al., 1999] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.
Cite as

Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ICALP.2021.36,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Labourel, Arnaud and Pelc, Andrzej},
  title =	{{Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.36},
  URN =		{urn:nbn:de:0030-drops-141051},
  doi =		{10.4230/LIPIcs.ICALP.2021.36},
  annote =	{Keywords: treasure hunt, graph, mobile agent}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.15
Distance Labeling Schemes for Cube-Free Median Graphs

Authors: Victor Chepoi, Arnaud Labourel, and Sébastien Ratel

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
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 using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.
Cite as

Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance Labeling Schemes for Cube-Free Median Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chepoi_et_al:LIPIcs.MFCS.2019.15,
  author =	{Chepoi, Victor and Labourel, Arnaud and Ratel, S\'{e}bastien},
  title =	{{Distance Labeling Schemes for Cube-Free Median Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.15},
  URN =		{urn:nbn:de:0030-drops-109598},
  doi =		{10.4230/LIPIcs.MFCS.2019.15},
  annote =	{Keywords: median graphs, labeling schemes, distributed distance computation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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