Allowable processing orders in the accelerated cascade algorithm

DOI10.1016/0166-218X(86)90083-1MaRDI QIDQ1072941zbMATH OpenFDO

Authors A. J. Goldman, Prasoon Tiwari

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(86)90083-1

zbMATH Keywords

accelerated versionall shortest distances cascade algorithmprocessing-order for distance-matrix entries

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Review text

We deal with the 'accelerated' version of \textit{O. Bilde} and \textit{J. Krarup} [Metra 8, 231-241 (1969)] of the 'all shortest distances' cascade algorithm due to \textit{B. A. Farbey, A. H. Land} and \textit{J. D. Murchland} [Manage. Sci., Theory 14, 19-28 (1967; Zbl 0183.236)]. A set of weakest possible conditions on the processing-order for distance-matrix entries, under which the Bilde-Krarup acceleration remains valid, is determined. These conditions are weaker than those of \textit{T. C. Hu} [SIAM J. Appl. Math. 15, 207-218 and 1517 (1967; Zbl 0158.154)] for the original algorithm, and in particular imply that the simple processing order of the original algorithm remains admissible for the accelerated version.

Recommendations

• A new class of asynchronous iterative algorithms with order intervals
• Preemptive multiprocessor order scheduling to minimize total weighted flowtime
• Parallel pipelined filter ordering with precedence constraints
• Efficient algorithms for order basis computation
• The impact of processing order on performance: a taxonomy of semi-FIFO policies
• An efficient algorithm for partial order production
• An efficient algorithm for partial order production
• Asynchronous Fault-Tolerant Total Ordering Algorithms
• An efficient design and implementation of the in-parameter-order algorithm

Cites work

• Algebraic structures for transitive closure
• Allowable processing orders in the accelerated cascade algorithm
• Finding the K Shortest Loopless Paths in a Network
• scientific article; zbMATH DE number 3244267 (Why is no real title available?)
• scientific article; zbMATH DE number 3302127 (Why is no real title available?)
• scientific article; zbMATH DE number 3400691 (Why is no real title available?)
• Iterative methods for determining the k shortest paths in a network
• NP-Complete operations research problems and approximation algorithms
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• Revised Matrix Algorithms for Shortest Paths
• The Cascade Algorithm for Finding all Shortest Distances in a Directed Graph

Cited in

(3)

• Allowable processing orders in the accelerated cascade algorithm
• scientific article; zbMATH DE number 1258209 (Why is no real title available?)
• scientific article; zbMATH DE number 1775510 (Why is no real title available?)

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Allowable processing orders in the accelerated cascade algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072941)