Decomposition algorithms for finding the shortest path between a source node and a sink node of a network

Suleyman Tufekci

Naval Research Logistics Quarterly, 1983, vol. 30, issue 3, 387-396

Abstract: Decomposition algorithms for finding a shortest path between a source node and a sink node of an arbitrary distance network are developed. Different decomposition algorithms are proposed for different network topologies. Since Shier's algorithm compares very favorably with other decomposition algorithms in all the network topologies, we compare our algorithms against Shier's algorithm. It is shown that the efficiency of the proposed algorithms compares very favorably with Shier's algorithm. For special types of networks the computational requirements of the proposed algorithm is a polynomial of O(n2).

Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800300303

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:wly:navlog:v:30:y:1983:i:3:p:387-396

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().