Name
Abstract | ||
|---|---|---|
Finding single-source shortest paths (i.e., from a source node to all other nodes) faster than ever may directly benefit a number of fields including communication networks, VLSI designs, and transportation networks. In this paper, we propose a novel hardware-assisted parallel shortest path algorithm derived from the ball string model. The algorithm can find single-source shortest paths for both undirected and directed graphs with the run-time complexity of O(L), where L is the length of the shortest path from the source to the farthermost node. The proposed algorithm has been implemented in Verilog, simulated, and synthesized to verify its correctness and run-time complexity. |
Year | Venue | Keywords |
|---|---|---|
2009 | CDES | parallel algorithm,ball string model,index terms: single source shortest path,hardware implementation.,indexing terms,time complexity,shortest path,vlsi design,shortest path algorithm,directed graph |
Field | DocType | Citations |
Combinatorics,Shortest path problem,Constrained Shortest Path First,Distance,Theoretical computer science,Yen's algorithm,Shortest Path Faster Algorithm,Mathematics,Widest path problem,K shortest path routing,Euclidean shortest path | Conference | 1 |
PageRank | References | Authors |
0.36 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tuo Shi | 1 | 5 | 1.52 |
| Jaehwan John Lee | 2 | 104 | 16.97 |