Mini-Project on Graph EmbeddingsClass number: 202-1-4071Schedule: Tue. l0:00-12:00Bldng ??, Auditorium ?? Office Hours: Thur. 14:00-16:00Bldng 37, Auditorium 217 OutlineThe aim of this mini-project is to familiarize students with the research in the area. The students will be required to read a paper or two on this subject, to implement an algorithm described in this paper, and to experiment with this algorithm. General informationThere will be one lecture on
Tue. 10:00-12:00, Nov. 1, in Building ??, Hall ??.
On this lecture the students will be introduced
to the area, and will be told about the papers they can choose. Within three
weeks after the beginning of the semester, the students are supposed to
choose a paper, and to inform the teacher of their choice. The work can be
done in pairs. SyllabysThe focus in this mini-project will be on the algorithms for constructing spanners. Intuitively, spanner can be seen as a sparse skeleton of the original graph that approximates many of its original properties. Spanners constitute an important tool in algorithmic design. They were used, in particular, for designing efficient algorithms for computing approximately shortest paths, and for various distributed tasks, such as routing and network synchronization. Students will be encouraged either to explore the basic graph-theoretic properties of spanners, or one of their algorithmic applications. Students interested in geometry will be given an opportunity to explore the concept of Euclidean Spanner, which plays a major role in designing algorithms for various geometrical problems. Projects
Graph
Spanners,
On
sparse spanners of weighted graphs,
Sparse partitions,
Fast
algorithms for constructing t-spanners and paths with stretch t.
Linear
Time Algorithm for Computing a (2k-1)-spanner of O(n*{1+1/k})
size in weighted graphs.
A
graph-theoretic game and its application to the k-server problem.
Probablistic approximation of metric spaces and its
algorithmic applications.
(1+e,b)-Spanner
Constructions for General Graphs,
Streaming and Fully Dynamic Centralized Algorithms for Constructing and
Maintaining Sparse Spanners, |