Name
Abstract | ||
|---|---|---|
In this paper we consider the problem of finding a shortest path from a source node to a fixed target node (SSP) or to all the nodes (SPT) on a directed graph. A family of algorithms which derives from the known auction algorithm is introduced. The key feature of these algorithms is based on topological transformations operated on the graphs that replace an optimal sub-path with a single arc of the same length (graph collapsing concept). The same idea is applied both to the standard auction algorithm and to a modified version of the algorithm. In the last mentioned case a good saving in computation cost is obtained as shown by the reported numerical examples. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1023/A:1011246118315 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
shortest path,network optimization,auction technique | Mathematical optimization,Path (graph theory),Shortest path problem,Directed graph,Algorithm,Shortest Path Faster Algorithm,Auction algorithm,Longest path problem,Mathematics,Widest path problem,K shortest path routing | Journal |
Volume | Issue | ISSN |
18 | 3 | 1573-2894 |
Citations | PageRank | References |
1 | 0.37 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Cerulli | 1 | 252 | 23.85 |
| P. Festa | 2 | 67 | 4.51 |
| Giancarlo Raiconi | 3 | 118 | 15.08 |