A Decomposition Algorithm for the Shortest-Route Problem

Gordon Mills

Operations Research, 1966, vol. 14, issue 2, 279-291

Abstract: There are a number of methods for finding the shortest routes between all pairs of points in a network; even with the aid of modern electronic computers; however, it is difficult to apply these methods to large networks, partly because such an application requires a large amount of computer time but especially because it requires a very large amount of fast-access storage, capacity. The decomposition algorithm presented here is designed to facilitate the analysis of such networks; the basic idea is to decompose the network into parts, apply one of the existing (matrix) methods to each part separately, and then to reunite the parts. In addition to reducing greatly the required amount of fast-access storage that is required, the algorithm generally appreciably reduces the required computer time, provided the network is not too small.

Date: 1966
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.14.2.279 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:14:y:1966:i:2:p:279-291

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().