A study of multi-constraint shortest paths and related problems

The School of EECS is hosting the following progress review seminar

A study of multi-constraint shortest paths and related problems

Speaker: Ziyi Liu
Host: Dr Miao Xu

Abstract: The Multi-Constraint Shortest Path (MCSP) problem aims to find the shortest path between two nodes in a network subject to a given constraint set. It is studied to support multi-criteria decision-making on path-finding, and typically processed as a skyline path problem. However, the number of intermediate skyline paths becomes larger as the network size increases and the number of constraints grows, which brings about the dramatic growth of computational cost and further makes the existing index-based methods hardly capable of obtaining the complete exact results. In this talk, we will present our index-based methods to answer different types of MCSP queries: 1) the simplest version of MCSP queries with one constraint; 2) MCSP queries with a fixed constraint set; 3) MCSP queries with any combinations of constraints; and 4) Approximate MCSP queries.

Bio: Ziyi Liu is currently a PhD candidate in the School of Information Technology and Electrical Engineering, the University of Queensland, under the supervision of Prof. Wen Hua and Prof. Lei Li. He obtained MSc in Computer Science from the Queensland University of Technology and BSc in Applied Mathematics from Chongqing Normal University. He have been working in the area of spatiotemporal data management, including efficient route planning in dynamic or multiple constraints environments, exact and approximate algorithms with querying processing and indexing, and learning-based content analysis.