The K Shortest Paths Problem with Application to Routing

Abstract

Due to the computational complexity of finding almost shortest simple paths, we propose that identifying a larger collection of (nonbacktracking) paths is more efficient than finding almost shortest simple paths on positively weighted real-world networks. First, we present an easy to implement $O(m\log m+kL)$ solution for finding all (nonbacktracking) paths with bounded length $D$ between two arbitrary nodes on a positively weighted graph, where $L$ is an upperbound for the number of nodes in any of the $k$ outputted paths. Subsequently, we illustrate that for undirected Chung-Lu random graphs, the ratio between the number of nonbacktracking and simple paths asymptotically approaches $1$ with high probability for a wide range of parameters. We then consider an application to the almost shortest paths algorithm to measure path diversity for internet routing in a snapshot of the Autonomous System graph subject to an edge deletion process.

37 pages, 6 figures

References in corpus (5)

• Uncovering the overlapping community structure of complex networks in nature and society
• Approximating the largest eigenvalue of network adjacency matrices
• Dynamical Systems on Networks: A Tutorial
• Effect of edge removal on topological and functional robustness of complex networks
• Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure

Cited by in corpus (1)

• Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure