DROPS

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}
}

Search Results

Documents authored by Pigné, Yoann

Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms

Abstract

Cite as

Dynamic Graphs Generators Analysis: An Illustrative Case Study

Abstract

Cite as

Thanks for your feedback!

Could not send message