DROPS

Document

DOI: 10.4230/LIPIcs.TIME.2024.20

FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks

Authors: Giorgio Lazzarinetti, Sara Manzoni, Italo Zoppis, and Riccardo Dondi

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract

The analysis and summarization of temporal networks are crucial for understanding complex interactions over time, yet pose significant computational challenges. This paper introduces FastMinTC+, an innovative heuristic approach designed to efficiently solve the Minimum Timeline Cover (MinTCover) problem in temporal networks. Our approach focuses on the optimization of activity timelines within temporal networks, aiming to provide both effective and computationally feasible solutions. By employing a low-complexity approach, FastMinTC+ adeptly handles massive temporal graphs, improving upon existing methods. Indeed, comparative evaluations on both synthetic and real-world datasets demonstrate that our algorithm outperforms established benchmarks with remarkable efficiency and accuracy. The results highlight the potential of heuristic approaches in the domain of temporal network analysis and open up new avenues for further research incorporating other computational techniques, for example deep learning, to enhance the adaptability and precision of such heuristics.

Cite as

Giorgio Lazzarinetti, Sara Manzoni, Italo Zoppis, and Riccardo Dondi. FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lazzarinetti_et_al:LIPIcs.TIME.2024.20,
  author =	{Lazzarinetti, Giorgio and Manzoni, Sara and Zoppis, Italo and Dondi, Riccardo},
  title =	{{FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.20},
  URN =		{urn:nbn:de:0030-drops-212275},
  doi =		{10.4230/LIPIcs.TIME.2024.20},
  annote =	{Keywords: Temporal Networks, Activity Timeline, Timeline Cover, Vertex Cover, Optimization, Heuristic}
}

Search Results

Documents authored by Manzoni, Sara

FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message