The shortest-path problem is a fundamental problem in graph theory which has many applications that require quick interaction (e.g., travel, communicate or search) between any two points in a network. However, in practice we are often not only interested in computing a quickest path but rather in a path satisfying a combination of different constraints.
The problem of finding such a path is called constrained shortest-path problem (CSP). A constraint could be fuel consumption or toll fee in road networks; end-to-end delay or minimum bandwidth guarantees in communication networks, etc. Whereas the shortest-path problem can be solved in polynomial time, the CSP is known to be NP-hard. Existing work on CSP does not scale well on large networks and are slow. In this project, we will investigate the limitations of the existing work and develop nice properties to pre-compute a compressed data structure to efficiently answer CSP queries.
- This project requires students to have a strong background in data structure and algorithms and excellent programming skills C/C++/Java. ANU students are expected to have finished COMP3600 or have an equivalent experience.
Graph Research Lab#
Graph algorithms provide fundamental and powerful ways of exploiting the structure of graphs. Recent advances in machine learning, particularly deep learning, are also achieving remarkable results in a wide variety of application domains. Graph Research Lab @ ANU aims to investigate graph-related problems by marrying the best of two worlds: traditional graph algorithms and new machine learning techniques to bridging the gap between combinatorial generalisation and deep learning.
For further information about our team, visit our Github.