Paper Info
Title
A*Prune: an algorithm for finding K shortest paths subject to multiple constraints
Abstract
We present a new algorithm, A*Prune, to list (in order of increasing length) the first K multiple-constrained-shortest-path (KMCSP) between a given pair of nodes in a digraph in which each are is associated with multiple quality of-service (QoS) metrics. The algorithm constructs paths starting at the source and going towards the destination. But, at each iteration, the algorithm gets rid of all paths that are guaranteed to violate the constraints, thereby keeping only those partial paths that have the potential to be turned into feasible paths, from which the optimal paths are drawn. The choice of which path to be extended first and which path can be pruned depend upon a projected path cost function, which is obtained by adding the cost already incurred to get to an intermediate node to an admissible cost to go the remaining distance to the destination. The Dijkstra's shortest path algorithm is a good choice to give a good admissible cost. Experimental results show that A*Prune is comparable to the current best known ε-approximate algorithms for most of randomly generated graphs, BA*Prune, which combines the A*Prune with any known polynomial time ε-approximate algorithms to give either optimal or ε-approximate solutions to the KMCSP problem, is also presented
Year
DOI
Venue
2001
10.1109/INFCOM.2001.916263
INFOCOM
Keywords
Field
DocType
optimisation,polynomial time ϵ-approximate algorithms,dijkstra's shortest path algorithm,qos routing,quality of service,optimal solutions,quality of-service,—shortest paths,optimal paths,ϵ-approximate solutions,search problems,polynomial approximation,np complete.,multi- ple constrained path selection,qos metrics,constraint based routing,projected path cost function,qos sensitive routing,multiple constraints,multiple-constrained-shortest-path,randomly generated graphs,graph theory,telecommunication network routing,a*prune algorithm,digraph nodes,admissible cost,ba*prune,dijkstra algorithm,jitter,bandwidth,cost function,polynomials,shortest path algorithm,routing,shortest path
Graph theory,Mathematical optimization,Computer science,Algorithm,Yen's algorithm,Floyd–Warshall algorithm,Suurballe's algorithm,Shortest Path Faster Algorithm,Time complexity,Digraph,Dijkstra's algorithm
Conference
Volume
ISSN
ISBN
2
0743-166X
0-7803-7016-3
Citations 
PageRank 
References 
88
4.56
10
Authors
2
Name
Order
Citations
PageRank
Gang Liu1884.56
K. G. Ramakrishnan258798.53