*Result*: Exact and approximation algorithms for covering timeline in temporal graphs.
*Further Information*
*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]*
*Full text is not displayed to guests* *Login for full access*