BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T200141Z
UID:Seminar-dept-339@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20140114T160000
DTEND:20140114T170000
SUMMARY:School Seminar Series
DESCRIPTION:Prof Guy Kortsarz: A survey on approximating spanners\n\nGiven an edge weighted graph G(V,E) a k-spanner of this graph is a graph G'(V,E') so that for every vertex pair, their distance in G' increases by no more than k factor compared to G.\n\n\n\nSpanners have applications in routing over the internet, making asynchronous distributed system into a synchronous one, biology and much more.\n\n\n\nOur goal, usually, is to get a spanner with few edges, and/or low cost. For example, I will show that there always exists a 3-spanner with O(n\sqrt{n}) edges and for some graph this is best possible.\n\n\n\nThe talk is a survey and large parts of it should be understood by people with basic knowledge of graphs and NP completeness.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=339
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR