BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T101638Z
UID:Seminar-dept-1060@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230713T130000
DTEND:20230713T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Alexandru Popa: Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms\n\nIn 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.\n\n\n\nJoint work with Riccardo Dondi\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1060
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR