Mini-Project on Graph Embeddings

 

Class number: 202-1-4071

Schedule: Mon. l0:00-12:00

Bldng 90, Auditorium 242

Office Hours: Tue. 14:00-16:00

Bldng 37, Office num. 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 Mon. 10:00-12:00, Oct. 15, in Building 90, Hall 242. 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.

From that point on, every three weeks each team (single student or a pair of students) should contact the teacher and set an appointment, on which the progress of the team will be evaluated. These meetings will also be used for consulting the teacher concerning the problems that arose during the research.

On the last meeting the students will present their final project. This last meeting should take place before the end of the examination period of the autumn semester.

The grade will be composed from: 60% evaluation of the final project, and 40% evaluation of the progress of the pair throughout the semester.

All the correspondence between the students and the teacher should be conducted through email; phone calls should be used only for very urgent affairs, or if the teacher failed to answer student's email within a period of one week (hopefully, this won't happen).

Projects' reports should be written in English.

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

  • D. Peleg and A.~Sch\"affer,

Graph Spanners,
J. Graph Theory, 13 (1989), pp. 99--116

  • I. Alth\"ofer, G. Das, D. Dobkin, D. Joseph, and J. Soares,

On sparse spanners of weighted graphs,
Discrete Comput. Geom., 9 (1993), pp. 81--100.

  • B. Awerbuch and D. Peleg,

Sparse partitions,
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 503--513.

  • E. Cohen,

Fast algorithms for constructing t-spanners and paths with stretch t.
Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 648-658,1993

  • S. Baswana and S. Sen,

Linear Time Algorithm for Computing a (2k-1)-spanner of O(n*{1+1/k}) size in weighted graphs.
Proc. of the 30th International Colloq. on Automata, Languages and Computing, ICALP 2003, pp. 284-296

  • N. Alon, R. Karp, D. Peleg and D. West,

A graph-theoretic game and its application to the k-server problem.
SIAM J. Comput., 24:78-100, 1995.

  • Y. Bartal,

Probablistic approximation of metric spaces and its algorithmic applications.
Proc. 37th IEEE Symp. on Foundations of Computer Science, pp. 184-193, 1996.

  • M. Elkin and D. Peleg,

(1+e,b)-Spanner Constructions for General Graphs,
SIAM J. Comput. 33(3): 608-631 (2004)

  • M. Elkin

Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners,
ICALP pp. 716-727 (2007)

 

Requirements for the Mini-Project Report

  • An email letter specifying the requirements,

An outlook letter - opens only from Windows