link

November 8, Tuesday
12:00 – 13:30

Approximating graphs by spanning trees
Computer Science seminar
Lecturer : Dr. Ofer Neiman
Lecturer homepage : http://www.cs.bgu.ac.il/~neimano/
Affiliation : CS, BGU
Location : 201/37
Host : Dr. Aryeh Kontorovich
Approximating an arbitrary graph by a simpler structure while preserving some properties of the original graph, is a very active research direction that has found numerous applications.In this talk we will discuss the problem of finding a spanning tree that preserves the distances of the original graph on average, up to a universal constant. Based on joint work with Ittai Abraham and Yair Bartal.