Course Identification

Succinct graph structures and their applications
20184152

Lecturers and Teaching Assistants

Prof. Merav Parter
Dr. Yinon Nahum

Course Schedule and Location

2018
Second Semester
Wednesday, 11:00 - 12:30, Ziskind, Rm 155
28/03/2018

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; 2.00 points

Comments

N/A

Prerequisites

No

Restrictions

50

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

50%
50%

Evaluation Type

Final assignment

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

3

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

Website

N/A