DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2024.8

On Inefficiently Connecting Temporal Networks

Authors: Esteban Christiann, Eric Sanlaville, and Jason Schoeters

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

Abstract

A temporal graph can be represented by a graph with an edge labelling, such that an edge is present in the network if and only if the edge is assigned the corresponding time label. A journey is a labelled path in a temporal graph such that labels on successive edges of the path are increasing, and if all vertices admit journeys to all other vertices, the temporal graph is temporally connected. A temporal spanner is a sublabelling of the temporal graph such that temporal connectivity is maintained. The study of temporal spanners has raised interest since the early 2000’s. Essentially two types of studies have been conducted: the positive side where families of temporal graphs are shown to (deterministically or stochastically) admit sparse temporal spanners, and the negative side where constructions of temporal graphs with no sparse spanners are of importance. Often such studies considered temporal graphs with happy or simple labellings, which associate exactly one label per edge. In this paper, we focus on the negative side and consider proper labellings, where multiple labels per edge are allowed. More precisely, we aim to construct dense temporally connected graphs such that all labels are necessary for temporal connectivity. Our contributions are multiple: we present exact or asymptotically tight results for basic graph families, which are then extended to larger graph families; an extension of an efficient temporal graph labelling generator; and overall denser labellings than previous work, whether it be global or local density.

Cite as

Esteban Christiann, Eric Sanlaville, and Jason Schoeters. On Inefficiently Connecting Temporal Networks. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{christiann_et_al:LIPIcs.SAND.2024.8,
  author =	{Christiann, Esteban and Sanlaville, Eric and Schoeters, Jason},
  title =	{{On Inefficiently Connecting Temporal Networks}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-198867},
  doi =		{10.4230/LIPIcs.SAND.2024.8},
  annote =	{Keywords: Network design principles, Network dynamics, Paths and connectivity problems, Branch-and-bound}
}

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

Search Results

Documents authored by Sanlaville, Éric

On Inefficiently Connecting Temporal Networks

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message