2 Search Results for "Magnien, Clémence"

Document
DOI: 10.4230/LIPIcs.SAND.2025.8
Matching and Edge Cover in Temporal Graphs

Authors: Lapo Cioni, Riccardo Dondi, Andrea Marino, Jason Schoeters, and Ana Silva

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Temporal graphs are a special class of graphs for which a temporal component is added to edges, that is, each edge possesses a set of times at which it is available and can be traversed. Many classical problems on graphs can be translated to temporal graphs, and the results may differ. In this paper, we define the {Temporal Edge Cover} and {Temporal Matching} problems and show that they are NP-complete even when fixing the lifetime or when the underlying graph is a tree. We then describe two FPT algorithms, with parameters lifetime and treewidth, that solve the two problems. We also find lower bounds for the approximation of the two problems and give two approximation algorithms which match these bounds. Finally, we discuss the differences between the problems in the temporal and the static framework.
Cite as

Lapo Cioni, Riccardo Dondi, Andrea Marino, Jason Schoeters, and Ana Silva. Matching and Edge Cover in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cioni_et_al:LIPIcs.SAND.2025.8,
  author =	{Cioni, Lapo and Dondi, Riccardo and Marino, Andrea and Schoeters, Jason and Silva, Ana},
  title =	{{Matching and Edge Cover in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.8},
  URN =		{urn:nbn:de:0030-drops-230614},
  doi =		{10.4230/LIPIcs.SAND.2025.8},
  annote =	{Keywords: graphs, temporal graphs, edge cover, matching, parameterized algorithm, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.TIME.2023.3
LSCPM: Communities in Massive Real-World Link Streams by Clique Percolation Method

Authors: Alexis Baudin, Lionel Tabourier, and Clémence Magnien

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)

Abstract
Community detection is a popular approach to understand the organization of interactions in static networks. For that purpose, the Clique Percolation Method (CPM), which involves the percolation of k-cliques, is a well-studied technique that offers several advantages. Besides, studying interactions that occur over time is useful in various contexts, which can be modeled by the link stream formalism. The Dynamic Clique Percolation Method (DCPM) has been proposed for extending CPM to temporal networks. However, existing implementations are unable to handle massive datasets. We present a novel algorithm that adapts CPM to link streams, which has the advantage that it allows us to speed up the computation time with respect to the existing DCPM method. We evaluate it experimentally on real datasets and show that it scales to massive link streams. For example, it allows to obtain a complete set of communities in under twenty-five minutes for a dataset with thirty million links, what the state of the art fails to achieve even after a week of computation. We further show that our method provides communities similar to DCPM, but slightly more aggregated. We exhibit the relevance of the obtained communities in real world cases, and show that they provide information on the importance of vertices in the link streams.
Cite as

Alexis Baudin, Lionel Tabourier, and Clémence Magnien. LSCPM: Communities in Massive Real-World Link Streams by Clique Percolation Method. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baudin_et_al:LIPIcs.TIME.2023.3,
  author =	{Baudin, Alexis and Tabourier, Lionel and Magnien, Cl\'{e}mence},
  title =	{{LSCPM: Communities in Massive Real-World Link Streams by Clique Percolation Method}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.3},
  URN =		{urn:nbn:de:0030-drops-190932},
  doi =		{10.4230/LIPIcs.TIME.2023.3},
  annote =	{Keywords: Temporal network, Link stream, k-clique, Community detection, Clique Percolation Method, Real-world interactions}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023

  • Refine by Author
  • 1 Baudin, Alexis
  • 1 Cioni, Lapo
  • 1 Dondi, Riccardo
  • 1 Magnien, Clémence
  • 1 Marino, Andrea
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Matchings and factors
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 1 Clique Percolation Method
  • 1 Community detection
  • 1 Link stream
  • 1 Real-world interactions
  • 1 Temporal network
  • 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