We consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor O ( T log n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(T \log {n})$$\end{document} , on a temporal graph of T timestamps and n vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a 4 ( T - 1 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4(T-1)$$\end{document} approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution.

(2024). Exact and approximation algorithms for covering timeline in temporal graphs [journal article - articolo]. In ANNALS OF OPERATIONS RESEARCH. Retrieved from https://hdl.handle.net/10446/279409

Exact and approximation algorithms for covering timeline in temporal graphs

Dondi, Riccardo;
2024-01-01

Abstract

We consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor O ( T log n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(T \log {n})$$\end{document} , on a temporal graph of T timestamps and n vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a 4 ( T - 1 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4(T-1)$$\end{document} approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution.
articolo
2024
Dondi, Riccardo; Popa, Alexandru
(2024). Exact and approximation algorithms for covering timeline in temporal graphs [journal article - articolo]. In ANNALS OF OPERATIONS RESEARCH. Retrieved from https://hdl.handle.net/10446/279409
File allegato/i alla scheda:
File Dimensione del file Formato  
AOR2024.pdf

accesso aperto

Versione: publisher's version - versione editoriale
Licenza: Creative commons
Dimensione del file 495.79 kB
Formato Adobe PDF
495.79 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/279409
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact