A fault-tolerant approach for the shortest path algorithm in large spectrum graphs. (c2007)

Abstract

This work proposes a solution for the shortest path algorithm for large spectrum graphs. The problem is of particular interest for applications in computer networks as well as in road networks. We tackle this problem in two stages. In the first stage an evolutionary algorithm for networks-based applications is formulated with a special interest emphasis on fault-tolerance, an important issue due to dynamic changes in routing configuration. In the second phase, we tackle large spectrum graphs where the evolutionary algorithm is applied using database constructs. Thus, the graph is stored in a database and the evolutionary algorithm is formulated using SQL queries. The operators as well as the selection operators are all database-based. The algorithm is attempted on the DIMACS challenge for the USA routes and favorable results are reported.