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

time complexityBoolean matrix multiplicationoutput-sensitive algorithmrectangular matrix multiplication

Mathematics Subject Classification ID

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

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

• 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?)
• Algorithms – ESA 2004
• All-pairs bottleneck paths in vertex weighted graphs
• Automata, Languages and Programming
• 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
• Faster algorithms for finding lowest common ancestors 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
• A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
• scientific article; zbMATH DE number 1405674 (Why is no real title available?)
• A note on Boolean matrix multiplication
• Characteristic matrix of covering and its application to Boolean matrix decomposition
• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• An improved bound on Boolean matrix multiplication for highly clustered data.
• Fast Output-Sensitive Matrix Multiplication
• scientific article; zbMATH DE number 4133979 (Why is no real title available?)
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• scientific article; zbMATH DE number 1223727 (Why is no real title available?)
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Efficiently correcting matrix products
• Speeding up the four Russians algorithm by about one more logarithmic factor
• Fast practical algorithms for the Boolean-product-witness-matrix problem
• scientific article; zbMATH DE number 1830739 (Why is no real title available?)
• Probabilistic tensors and opportunistic Boolean matrix multiplication

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)