1 Search Results for "Corsini, Timothée"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Casteigts, Arnaud
  • 1 Corsini, Timothée
  • 1 Hocquard, Hervé
  • 1 Labourel, Arnaud

  • Refine by Classification
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Networks → Network dynamics
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 1 Dynamic networks
  • 1 Longest path
  • 1 Rooted minors
  • 1 Series-parallel graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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