Seminar of Theoretical Computer Science - Alexandru Popa (29.9.2023)

Friday 29.9.2023 at 13:00, Lecture room M 213

---

prof. Alexandru Popa  (Faculty of Mathematics and Computer Science, University of Bucharest):
Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms

Abstract:
In this talk we present 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. 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.

Joint work with Riccardo Dondi

 

 

---