On Single Source Shortest Journey Problem in Temporal Graphs

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "On Single Source Shortest Journey Problem in Temporal Graphs"

by

GAO Zhimeng

Abstract:

Temporal graphs are directed graphs in which the traversal time and weights of 
edges vary across time intervals. A journey in a temporal graph is defined as a 
path that traverses edges in chronological order. This project focuses on the 
problem setting where the total cost of a journey is equivalent to the 
cumulative sum of edge weights of the edges traversed along a path. We proved 
the NP-hardness of this problem, and established an exponential lower bound for 
the number of intervals in the plot of the shortest journey cost from the 
source to a vertex against time. Given the NP-hardness, we proposed a FPT $(1 + 
\epsilon)$-approximation algorithm for computing single source shortest journey 
in temporal graphs.


Date            : 29 April 2024 (Monday)

Time            : 11:00 - 11:40

Venue           : Room 5560 (near lifts 27/28), HKUST

Advisor         : Prof. CHENG Siu-Wing

2nd Reader      : Dr. ARYA Sunil