Treffer: Reducing Space Requirements for Shortest Path Problems.

The problem of determining the shortest path through a level network using as little space as possible is considered. Let k denote the number of levels and assume each level contains m nodes. A space efficient technique is presented by which the shortest route from a source to a sink may be found in a complete level graph using theta(m + k) storage locations and a factor of only theta(log k) more basic operations than space inefficient methods. If an edge from node p of level l to node q of level l + 1 exists only if p is greater than or equal to q, then the space saving technique may also be employed. In this case the run time of the algorithm is at most twice that of conventional approaches. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)