Computing transitive closure on systolic arrays of fixed size

DOI10.1007/BF02252956MaRDI QIDQ808290zbMATH OpenOpenAlexFDO

Authors Björn Lisper

Publication date 1991

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02252956

zbMATH Keywords

shortest pathtransitive closuresystolic arrayarray partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Numerical Analysis and Its Applications
• Efficient computation of transitive closures
• scientific article; zbMATH DE number 4185046
• Algorithms for transitive closure
• Abstract derivation of transitive closure algorithms
• An experimental study of dynamic algorithms for transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• An experimental study of algorithms for fully dynamic transitive closure

Cites work

• A Theorem on Boolean Matrices
• A block algorithm and optimal fixed-size systolic array processor for the algebraic path problem
• A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)
• A transitive closure algorithm
• An orthogonal systolic array for the algebraic path problem
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• On the Analysis and Synthesis of VLSI Algorithms
• Parallel Matrix and Graph Algorithms
• Parallel computation and conflicts in memory access
• Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
• Synthesis of a new systolic architecture for the algebraic path problem
• Synthesizing linear array algorithms from nested FOR loop algorithms
• Synthesizing synchronous systems by static scheduling in space-time
• The space complexity of pebble games on trees
• Transitive closure and related semiring properties via eliminants

Cited in

(11)

• Size-estimation framework with applications to transitive closure and reachability
• scientific article; zbMATH DE number 2089168 (Why is no real title available?)
• The transitive closure and related algorithms of digraph on the reconfigurable architecture
• Numerical Analysis and Its Applications
• scientific article; zbMATH DE number 4185046 (Why is no real title available?)
• Mapping dynamic programming onto modular linear systolic arrays
• scientific article; zbMATH DE number 4035176 (Why is no real title available?)
• Efficient computation of transitive closures
• scientific article; zbMATH DE number 4092728 (Why is no real title available?)
• scientific article; zbMATH DE number 1941144 (Why is no real title available?)
• scientific article; zbMATH DE number 1849117 (Why is no real title available?)

This page was built for publication: Computing transitive closure on systolic arrays of fixed size

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