A fast output-sensitive algorithm for Boolean matrix multiplication

DOI10.1007/S00453-010-9441-XMaRDI QIDQ634680zbMATH OpenOpenAlexFDO

Authors Andrzej Lingas

Publication date 16 August 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-010-9441-x

zbMATH Keywords

Boolean matrix multiplicationoutput-sensitive algorithmrectangular matrix multiplicationtime complexity

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• Fast practical algorithms for the Boolean-product-witness-matrix problem
• On minimum witnesses for Boolean matrix multiplication
• Fast Output-Sensitive Matrix Multiplication
• An improved algorithm for Boolean matrix multiplication

Cites work

• All-pairs bottleneck paths in vertex weighted graphs
• Complexity of monotone networks for Boolean matrix product
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Efficient determination of the transitive closure of a directed graph
• Fast recognition of pushdown automaton and context-free languages
• Fast rectangular matrix multiplication and applications
• Fast sparse matrix multiplication
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 3497801 (Why is no real title available?)
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• LCA queries in directed acyclic graphs
• Matrix multiplication via arithmetic progressions
• Min-wise independent permutations
• On a set of almost deterministic k-independent random variables
• On the power of two-point based sampling
• PRIMES is in P
• Rectangular matrix multiplication revisited
• Structure prediction and computation of sparse matrix products
• Subcubic equivalences between graph centrality problems, APSP and diameter
• The Power of Negative Thinking in Multiplying Boolean Matrices

Cited in

(17)

• An improved algorithm for Boolean matrix multiplication
• Efficiently correcting matrix products
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• scientific article; zbMATH DE number 4133979 (Why is no real title available?)
• Fast Output-Sensitive Matrix Multiplication
• Fast practical algorithms for the Boolean-product-witness-matrix problem
• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• Bulk-synchronous parallel multiplication of Boolean matrices
• Fast Boolean matrix multiplication for highly clustered data
• Erratum: Bulk-synchronous parallel multiplication of Boolean matrices
• Probabilistic tensors and opportunistic Boolean matrix multiplication
• Speeding up the four Russians algorithm by about one more logarithmic factor
• A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• An improved bound on Boolean matrix multiplication for highly clustered data.
• A note on Boolean matrix multiplication
• Characteristic matrix of covering and its application to Boolean matrix decomposition

This page was built for publication: A fast output-sensitive algorithm for Boolean matrix multiplication

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