BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260512T165523Z
UID:Seminar-dept-1006@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20220517T100000
DTEND:20220517T110000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Kitty Meeks: Counting Temporal Paths\n\nThe betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. I will explain how, for several natural notions of optimality (including foremost or fastest temporal paths) this counting problem reduces to #Temporal Path, the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #Temporal Path is #P-hard in general. In this talk I will describe recent progress towards a systematic study of the parameterised and approximation complexity of #Temporal Path, including strong intractability results and some exact and approximate FPT algorithms for special cases.\n\n\n\nThis is joint work with Jessica Enright (Glasgow) and Hendrik Molter (Ben-Gurion University of the Negev).\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1006
LOCATION:Zoom
END:VEVENT
END:VCALENDAR