Single Source Shortest Paths (SSSP) Problem on Dynamic Graphs

PhD Qualifying Examination


Title: "Single Source Shortest Paths (SSSP) Problem on Dynamic Graphs"

by

Mr. Zijian LI


Abstract:

The single source shortest path (SSSP) problem is one of the most 
fundamental and classic topics in graph theory, which is one of the key 
problem in a large amount of real world applications. In this survey, we 
focus on the approaches which solves the SSSP problem on dynamic graphs. 
The dynamic graphs are graphs whose vertices and edges can be inserted and 
deleted, while the attributes of edges can be updated. The major 
difference between our survey and previous ones is that, our survey 
provides detailed illustrations of methods which solve the SSSP problem on 
both centralized and distributed systems, while the previous surveys only 
consider the centralized algorithms designed for single machine. We also 
show that the centralized algorithms cannot be simply applied to 
distributed systems due to the characteristics of distributed graph 
storage. Another difference between our survey and previous ones is that, 
most previous surveys  only discusses the exact solutions for the SSSP 
problem on dynamic graphs. However, many real-world applications do not 
always require an exact shortest path, and an approximate one with some 
quality guarantee is also acceptable especially in real-time applications 
where the responsiveness is far more important than the accuracy. 
Therefore, in this survey, we also provide detailed discussions on the 
approximate solutions for centralized dynamic graphs.


Date:			Monday, 31 July 2017

Time:                  	5:00pm - 7:00pm

Venue:                  Room 2612A
                         Lifts 31/32

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Shing-Chi Cheung (Chairperson)
 			Dr. Kai Chen
 			Dr. Xiaojuan Ma


**** ALL are Welcome ****