3 Search Results for "Pigné, Yoann"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.27
Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

Authors: Michelle Döring

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Temporal graphs model networks whose connections are available only at specific points in time. Several definitional subtleties - whether paths must follow strictly increasing time labels (strict vs. non-strict), whether adjacent edges cannot appear simultaneously (proper), and whether edges are forbidden to appear multiple times (simple) - give rise to different temporal graph settings. These distinctions directly impact the definition of temporal reachability, a core concept in temporal graph theory. Casteigts, Corsini, and Sarkar [TCS24] introduced a framework of equivalence notions to compare the expressive power of these settings focusing solely on undirected temporal graphs. In this work, we extend their framework to include the fundamental dimension of directed vs. undirected. Our contribution is three-fold. We (1) complete the undirected hierarchy by resolving the two open questions from [TCS24], (2) fully characterize the hierarchy of the directed settings, and (3) compare the directed and undirected settings, showing that directed temporal graphs are strictly more expressive than undirected temporal graphs in terms of reachability. Our structural results highlight both the limitations and strengths of various temporal graph settings - for example, directed + strict + simple graphs can realize every possible reachability graph, while directed + proper graphs necessarily induce at least one transitive reachability on each directed cycle. We also provide transformation procedures between temporal settings offering practical tools for transferring algorithms and hardness results across models.
Cite as

Michelle Döring. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doring:LIPIcs.ISAAC.2025.27,
  author =	{D\"{o}ring, Michelle},
  title =	{{Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.27},
  URN =		{urn:nbn:de:0030-drops-249353},
  doi =		{10.4230/LIPIcs.ISAAC.2025.27},
  annote =	{Keywords: temporal graphs, directed graphs, temporal reachability, dynamic networks}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.24
Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms

Authors: Stefan Balev, Yoann Pigné, Éric Sanlaville, and Mathilde Vernet

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
This note introduces an extension of the Steiner tree problem applied to dynamic graphs. It discusses its interest, studies its complexity and proposes an algorithm tested on generated and real data.
Cite as

Stefan Balev, Yoann Pigné, Éric Sanlaville, and Mathilde Vernet. Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 24:1-24:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balev_et_al:LIPIcs.SAND.2024.24,
  author =	{Balev, Stefan and Pign\'{e}, Yoann and Sanlaville, \'{E}ric and Vernet, Mathilde},
  title =	{{Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{24:1--24:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.24},
  URN =		{urn:nbn:de:0030-drops-199026},
  doi =		{10.4230/LIPIcs.SAND.2024.24},
  annote =	{Keywords: Steiner Tree, Dynamic Graph, Complexity, experimental study}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.8
Dynamic Graphs Generators Analysis: An Illustrative Case Study

Authors: Vincent Bridonneau, Frédéric Guinand, and Yoann Pigné

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
In this work, we investigate the analysis of generators for dynamic graphs, which are defined as graphs whose topology changes over time. We focus on generated graphs whose orders are neither growing nor constant along time. We introduce a novel concept, called "sustainability," to qualify the long-term evolution of dynamic graphs. A dynamic graph is considered sustainable if its evolution does not result in a static, empty, or periodic graph. To measure the dynamics of the sets of vertices and edges, we propose a metric, named "Nervousness," which is derived from the Jaccard distance. As an illustration of how the analysis can be conducted, we design a parametrized generator, named D3G3 (Degree-Driven Dynamic Geometric Graphs Generator), that generates dynamic graph instances from an initial geometric graph. The evolution of these instances is driven by two rules that operate on the vertices based on their degree. By varying the parameters of the generator, different properties of the dynamic graphs can be produced. Our results show that in order to ascertain the sustainability of the generated dynamic graphs, it is necessary to study both the evolution of the order and the Nervousness for a given set of parameters.
Cite as

Vincent Bridonneau, Frédéric Guinand, and Yoann Pigné. Dynamic Graphs Generators Analysis: An Illustrative Case Study. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bridonneau_et_al:LIPIcs.SAND.2023.8,
  author =	{Bridonneau, Vincent and Guinand, Fr\'{e}d\'{e}ric and Pign\'{e}, Yoann},
  title =	{{Dynamic Graphs Generators Analysis: An Illustrative Case Study}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.8},
  URN =		{urn:nbn:de:0030-drops-179443},
  doi =		{10.4230/LIPIcs.SAND.2023.8},
  annote =	{Keywords: Dynamic Graphs, Graph Generation, Graph Properties, Evolutionary models}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2024
  • 1 2023

  • Refine by Author
  • 2 Pigné, Yoann
  • 1 Balev, Stefan
  • 1 Bridonneau, Vincent
  • 1 Döring, Michelle
  • 1 Guinand, Frédéric
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Paths and connectivity problems
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Random graphs
  • 1 Networks → Network dynamics
  • 1 Networks → Topology analysis and generation
  • Show More...

  • Refine by Keyword
  • 1 Complexity
  • 1 Dynamic Graph
  • 1 Dynamic Graphs
  • 1 Evolutionary models
  • 1 Graph Generation
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact