• Exact and approximation algori...

Treffer: Exact and approximation algorithms for covering timeline in temporal graphs.

Title:
Exact and approximation algorithms for covering timeline in temporal graphs.
Authors:
Dondi, Riccardo1 (AUTHOR) riccardo.dondi@unibg.it, Popa, Alexandru2 (AUTHOR) alexandru.popa@fmi.unibuc.ro
Source:
Annals of Operations Research. Aug2025, Vol. 351 Issue 1, p609-628. 20p.
Subject Terms:
*NP-hard problems, *APPROXIMATION algorithms, *PARAMETERIZATION, *GRAPH theory, *TIME-varying networks, *ALGORITHMS, *MATHEMATICAL optimization
Database:
Academic Search Index

Weitere Informationen

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) , 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) approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution. [ABSTRACT FROM AUTHOR]

Der Volltext kann Gästen nicht angezeigt werden.