BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260531T003112Z
UID:Seminar-ACTO/Networks-752@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20191024T140000
DTEND:20191024T150000
SUMMARY:ACTO/Networks Series
DESCRIPTION:Argyrios Deligkas: Optimizing Reachability Sets in Temporal Graphs by Delaying\n\nA temporal graph is a dynamic graph, where every edge is assigned a set of integer  time labels that indicate at which discrete time step the edge is available. In this paper, we study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources.The questions about reachability sets are motivated by numerous applications of temporal graphs in network epidemiology, or scheduling problems in supply\nnetworks in manufacturing. We study the computational complexity of several optimization problems with different reachability objectives and in particular the\ncontrol mechanism based on natural operations of delaying time events. The first one, termed merging, is global and batches together consecutive time labels\nin the whole network simultaneously, which corresponds to postponing all events until a particular time. The second one, imposes independent delays on the\ntime labels of every edge of the graph. We provide a thorough investigation of the computational complexity of different objectives related to reachability sets\nwhen these operations are used. For the merging operation, we prove NP-hardness results for several minimization and maximization reachability objectives,\neven for very simple graph structures. For the second operation, we prove that the minimization problems are NP-hard when the number of allowed delays is\nbounded. We complement this with a polynomial-time algorithm for the case of unbounded delays.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=752
LOCATION:EEE 6.05
END:VEVENT
END:VCALENDAR