Course Identification
Succinct graph structures and their applications
Lecturers and Teaching Assistants
Prof. Merav Parter
Course Schedule and Location
Second Semester
Thursday, 10:15 - 12:00, Ziskind, Rm 1
23/04/2020
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points
Comments
Will be taught via Zoom starting April 19th.
Attendance and participation
Estimated Weekly Independent Workload (in hours)
Syllabus
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-server), routing in networks and spectral sparsification.
Learning Outcomes
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.
Reading List
Lecture notes for the course on my home page