Title :
I/O-efficiency of shortest path algorithms: an analysis
Author_Institution :
Dept. of Comput. Sci., ETH Zurich, Switzerland
Abstract :
To establish the behavior of algorithms in a paging environment, the author analyzes the input/output (I/O) efficiency of several representative shortest path algorithms. These algorithms include single-course, multisource, and all pairs ones. The results are also applicable for other path problems such as longest paths, most reliable paths, and bill of materials. The author introduces the notation and a model of a paging environment. The I/O efficiencies of the selected single-source, all pairs, and multisource algorithms are analyzed and discussed
Keywords :
database theory; directed graphs; programming theory; I/O-efficiency; all pairs algorithms; bill of materials; input/output efficiency; longest paths; most reliable paths; multisource algorithms; paging environment; path problems; shortest path algorithms; single source algorithms; Algebra; Algorithm design and analysis; Bills of materials; Computer science; Database languages; Graph theory; Materials reliability; Operations research; Reliability theory; Shortest path problem;
Conference_Titel :
Data Engineering, 1992. Proceedings. Eighth International Conference on
Conference_Location :
Tempe, AZ
Print_ISBN :
0-8186-2545-7
DOI :
10.1109/ICDE.1992.213212
