Efficient Algorithms for Distance Problems in Large Networks

点击翻译按钮获取中文摘要

The shortest distance/path problems in graphs are among the most fundamental problems in computer algorithms and have numerous applications in areas such as transportation, social and information networks. New applications such as those in Geographic Information Systems, intelligent transportation systems, social network analysis systems, and computer network management systems expect to get a real time answer for a distance query in large networks. Classical shortest path algorithms are inefficient for these new challenges which have received much attention recently. A major approach to address the new challenges is to develop two-phase algorithms which pre-compute some distance information and keep the information in a data structure, called oracle, in phase one and answer distance queries with the assistance of the oracle in phase two. The query time (time in phase two) and oracle size (memory space required by the oracle) are major criteria for evaluating the algorithms. A two-phase algorithm with a small query time and oracle size for a wide range of applications is of great importance to address the new challenges. A large number of two-phase algorithms have been developed. However there are limitations in these algorithms: their oracle sizes are too large for new applications in large networks; most algorithms are complex and difficult to implement, making them only theoretically interesting. The goals of this research are to develop new two-phase algorithms which are simple and easy to implement, and have small query time and oracle size in both theory and practice for new applications in large networks such as transportation networks, computer networks and complex social networks.