In this paper we study a variant of vertex cover on temporal graphs that has been recently introduced for timeline activities summarization in social networks. The problem has been proved to be NP-hard, even in restricted cases. In this paper, we present algorithmic contributions for the problem. First, we present an approximation algorithm of factor O(T log n), on a temporal graph of T timestamps and n vertices. Then, we consider the restriction where at most one temporal edge is defined in each timestamp. For this restriction, which has been recently shown to be NP-hard, we present a 4(T − 1) approximation algorithm and a parameterized algorithm when the parameter is the cost (called span) of the solution.

(2023). Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms . Retrieved from https://hdl.handle.net/10446/262329

Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms

Dondi, Riccardo;
2023-01-01

Abstract

In this paper we study a variant of vertex cover on temporal graphs that has been recently introduced for timeline activities summarization in social networks. The problem has been proved to be NP-hard, even in restricted cases. In this paper, we present algorithmic contributions for the problem. First, we present an approximation algorithm of factor O(T log n), on a temporal graph of T timestamps and n vertices. Then, we consider the restriction where at most one temporal edge is defined in each timestamp. For this restriction, which has been recently shown to be NP-hard, we present a 4(T − 1) approximation algorithm and a parameterized algorithm when the parameter is the cost (called span) of the solution.
2023
Dondi, Riccardo; Popa, Alexandru
File allegato/i alla scheda:
File Dimensione del file Formato  
Dondi_IWOCA23.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 834.41 kB
Formato Adobe PDF
834.41 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/262329
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact