|
Week
|
Topic
|
Lecturer
|
|
|
7/3/06
|
Introduction
|
Liam
|
|
|
Spanners
|
|
|
|
|
|
|
2
|
Fast
Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).
Donald Aingworth,
Chandra Chekuri, Piotr Indyk, Rajeev Motwani
|
Marina
|
|
|
3
|
All Pairs Almost
Shortest Paths
Dorit Dor, Shay
Halperin, Uri Zwick,
|
Eran
|
|
|
4
|
A Simple
Linear time Algorithm for Computing (2k-1)-spanner of O(n^{1+1/k}) size for
weighted graphs
Surender Baswana,
Sandeep Sen
|
Boaz
|
|
|
5
|
Approximate Distance Oracles for Unweighted
Graphs in O(n^2 log n) Time
Surender Baswana,
Sandeep Sen
|
Eti
|
|
|
6
|
New Constructions of (a,b)-Spanners and Purely
Additive Spanners
Surender Baswana,
Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
|
Dima
|
|
|
7
|
Spanners and emulators with sublinear distance
errors
Mikkel Thorup and
Uri Zwick
|
Yaron
|
|
|
8
|
Dynamic algorithms for
geometric spanners of small diameter: {Randomized} solutions
S.
Arya and D. M. Mount and M. Smid
|
Omri
|
|
|
9
|
A
decomposition of multidimensional point sets with applications to
k-nearest-neighbors and n-body potential fields
Paul B. Callahan
and S. Rao Kosaraju
|
Maxim
|
|
|
10
|
Euclidean
spanners: short, thin, and lanky
S.
Arya and G. Das and D. M. Mount and J. S. Salowe and M. Smid
|
|
|
|
11
|
Multiple-source
shortest paths in planar graphs
Philip N. Klein
|
Yevgeni
|
|
|
12
|
Preprocessing
an undirected planar network to enable fast approximate distance queries
Philip N. Klein
|
|
|
|
13
|
All-pairs
shortest paths for unweighted undirected graphs in o(mn) time
Timothy M. Chan
|
Yuval Shwartz
|
|
|
|
|
|
|