Efficient Maintenance of Highway Cover Labelling for Distance Queries on Large Dynamic Graphs

Abstract Graphs in real-world applications are typically dynamic that undergo rapid changes in their topological structure over time by either adding or deleting edges or vertices. However, it is challenging to design algorithms capable of supporting updates efficiently on dynamic graphs. In this paper, we devise a parallel fully dynamic labelling method to reflect changes on graphs for efficient shortest-path distance computation, a fundamental problem in graph theory. At its core, our solution accelerates query processing through a fully dynamic distance labelling with a limited size but providing a good approximation to bound online searches on dynamic graphs. Our parallel fully dynamic labelling method leverages two sources of efficiency gain: landmark parallelism and anchor parallelism. Furthermore, it can handle both incremental and decremental updates efficiently using a unified search approach and a bounded repairing inference mechanism. We theoretically analyze the correctness, labelling minimality and time complexity of our method, and also conduct extensive experiments to empirically verify its efficiency and scalability on 10 real-world large networks.