Succinct graph structures and their applications
Lecturers and Teaching Assistants
Prof. Merav Parter
Course Schedule and Location
Wednesday, 10:15 - 12:00, Ziskind, Rm 155
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points
Chemical Sciences: Elective; 2.00 points
Basic undergraduate knowledge in algorithms and graph theory.
Attendance and participation
Estimated Weekly Independent Workload (in hours)
Shortest paths in graphs are perhaps the most classical long-studied concept in graphs. The course will cover this area from three angles: graph structures, data structures and algorithms. Much attention will be devoted for graph spanners which are sparse subgraphs which faithfully preserve distances in the original graph up to some small stretch. We will discuss the graph-theoretic aspects of spanners, as well as related structures as probabilistic partitions, tree-cover and distance oracles. We will also present a wide range of algorithmic applications related to shortest-path computations, online problems (e.g., k-servers), routing in networks and spectral sparsification.
Upon successful completion of this course students should be able to:
(1) Familiarity with many graph structures and their computation in many computational settings.
(2) Introduction to distributed network algorithms.
(3) Exposition to recent research activity in the area of graph algorithms.
Lecture notes for the course on my home page