zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm. (English) Zbl 0776.90083
Summary: Four new shortest-path algorithms, two sequential and two parallel, for the source-to-sink shortest-path problem are presented and empirically compared with five algorithms previously discussed in the literature. The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of R. Dial, F. Glover, D. Karney and D. Klingman [Networks 9, 215-248 (1979; Zbl 0414.68035)] with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest-path algorithm. The new parallel algorithm, PS22, is based on S22 and is the best of the parallel algorithms. We also present results for three new S22-type shortest-path heuristics. These heuristics find very good (often optimal) paths much faster than the best shortest-path algorithm.
MSC:
90C35Programming involving graphs or networks
65Y05Parallel computation (numerical methods)
90-08Computational methods (optimization)
References:
[1]C. Berge and A. Ghouila-Houri,Programming, Games, and Transportation Networks, John Wiley and Sons, Inc., New York, NY, 1962.
[2]D. Bertsekas and R. Gallager,Data Networks, Prentice-Hall, Englewood Cliffs, NJ, 1987.
[3]G. Dantzig, ?On the shortest route through a network,?Mgmt. Sci. 6 (1960) 187-190. · Zbl 0995.90518 · doi:10.1287/mnsc.6.2.187
[4]N. Deo and C. Pang, ?Shortest-path algorithms: Taxonomy and annotation,?Networks 14 (1984) 275-323. · Zbl 0542.90101 · doi:10.1002/net.3230140208
[5]M. Desrochers, ?A note on the partitioning shortest path algorithm,?Oper. Res. Letters 6 (1987) 183-187. · Zbl 0641.90083 · doi:10.1016/0167-6377(87)90017-4
[6]R. Dial, ?Algorithm 360: Shortest path forest with topological ordering,?Commun. ACM,12 (1969) 632-633. · doi:10.1145/363269.363610
[7]R. Dial, F. Glover, D. Karney, and D. Klingman,A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees, CCS Report 291, Center for Cybernetic Studies, The University of Texas, Austin, TX 1977.
[8]R. Dial, F. Glover, D. Karney, and D. Klingman, ?A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees,?Networks 9 (1979) 215-250. · Zbl 0414.68035 · doi:10.1002/net.3230090304
[9]E. Dijkstra, ?A note on two problems in connexion with graphs,?Numerische Mathematik 1 (1959) 269-271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[10]J. Divoky, ?Improvements for the Thresh X2 shortest path algorithm,?Oper. Res. Letters 6 (1987) 227-232. · Zbl 0628.90088 · doi:10.1016/0167-6377(87)90053-8
[11]S. Dreyfus, ?An appraisal of some shortest-path algorithms,?Oper. Res. 17 (1969) 395-412. · Zbl 0172.44202 · doi:10.1287/opre.17.3.395
[12]S. Even,Graph Algorithms, Computer Science Press, Rockville, MD, 1979.
[13]G. Gallo, and S. Pallottino, ?Shortest path methods: A unifying approach,?Math. Programming Study 26 (1986) 38-64.
[14]G. Gallo, and S. Pallottino, ?Shortest path algorithms,?Ann. Oper. Res. 13 (1988) 3-79. · doi:10.1007/BF02288320
[15]F. Glover, R. Glover, and D. Klingman, ?Computational study of an improved shortest path algorithm,?Networks 14 (1984) 25-36. · doi:10.1002/net.3230140103
[16]F. Glover, D. Klingman, N. Phillips, and R. Schneider, ?New Polynomial Shortest Path Algorithms and Their Computational Attributes,?Mgmt. Sci. 31 (1985) 1106-1128. · Zbl 0609.90103 · doi:10.1287/mnsc.31.9.1106
[17]P. Hart, N. Nilsson, and B. Raphael, ?A formal basis for the heuristic determination of minimum cost paths,?IEEE Trans. of Systems Science and Cybernetics,SSC-4 (1968) 100-107. · doi:10.1109/TSSC.1968.300136
[18]T. Hu,Combinatorial Algorithms, Addison-Wesley, Reading, MA, (1982).
[19]P. Jensen and J. Barnes,Network Flow Programming, John Wiley and Sons, Inc., New York, NY, 1980.
[20]D. Klingman, J. Mote, and D. Whitman,Improving Flow Management and Control Via Improving Shortest Path Analysis, CCS Report 322, Center for Cybernetic Studies, The University of Texas, Austin, TX, 1978.
[21]E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, NY, 1987.
[22]T. Mohr and C. Pasche, ?A parallel shortest path algorithm,?Computing 40 (1988) 281-292. · Zbl 0659.68089 · doi:10.1007/BF02276912
[23]T. Nicholson, ?Finding the Shortest Route Between Two Points in a Network,?The Computer J. 9 (1966) 275-280.
[24]C. Papadimitriou, and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1987.
[25]I. Pohl,Bi-directional and Heuristic Search in Path Problems, SLAC Report No. 104, Stanford, CA, 1969.
[26]I. Pohl, ?Bi-directional Search,?Machine Intelligence, B. Meltzer and D. Michie, eds.,6 (1971) 127-140.
[27]M. Quinn,Designing Efficient Algorithms for Parallel Computers, McGraw-Hill, New York, NY, 1984.
[28]R. Rockafellar,Network flows and monotropic optimization, John Wiley and Sons, Inc., New York, NY, 1984.
[29]R. Tarjan,Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.