A Comparison between Graph-Compression and Landmark Shortest-Path Approaches

Abstract

Abstract—Shortest path improvement is one of the most important and recent issues in combinatorial optimization. Emergency routs, road and public transportation networks, routing schemes for computer networks, social networks, and other applications are all motivating the study of improving shortest path finding. One of the big obstacles in such real-word applications is the size of the graphs. Given a weighted graph G(V,E,w), an algorithm to improve classical shortest-path for a given source <s> is provided. The contribution of this paper is to study the improvement of finding shortest-path by compressing the graph while preserving the graph properties and comparing it with the approach of using landmark optimization. In this paper we implement the new approach of graph compression and the landmark approach. We discuss the performance, storage, error rate in our approach compared to landmark. The paper concludes that the new graph compression technique performs with no errors compared to fast landmark approach which is error prone when selecting source or destination vertices out of the landmark nodes.