Mini-Project on
Graph Embeddings
Class number:
202-1-4071
Schedule: Sun.
l0:00-12:00
Bldng 34, Auditorium 116 Office Hours: Tue.
14:00-16:00
Bldng 37, Auditorium 217 Outline
The 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
information
There will be one lecture on
Sun. 10:00-12:00, Oct. 22, in Building 34, Hall 116. 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. Syllabys
The 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, |