A fast output-sensitive algorithm for Boolean matrix multiplication
From MaRDI portal
Publication:634680
DOI10.1007/S00453-010-9441-XzbMATH Open1218.68195OpenAlexW2141293105MaRDI QIDQ634680FDOQ634680
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
Recommendations
time complexityBoolean matrix multiplicationoutput-sensitive algorithmrectangular matrix multiplication
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of monotone networks for Boolean matrix product
- Efficient determination of the transitive closure of a directed graph
- The Power of Negative Thinking in Multiplying Boolean Matrices
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- PRIMES is in P
- On a set of almost deterministic k-independent random variables
- Fast recognition of pushdown automaton and context-free languages
- On the power of two-point based sampling
- Title not available (Why is that?)
- Fast rectangular matrix multiplication and applications
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Rectangular matrix multiplication revisited
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Min-wise independent permutations
- All-pairs bottleneck paths in vertex weighted graphs
- Automata, Languages and Programming
- Algorithms – ESA 2004
- Structure prediction and computation of sparse matrix products
- Title not available (Why is that?)
- Subcubic equivalences between graph centrality problems, APSP and diameter
Cited In (17)
- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
- Speeding up the four Russians algorithm by about one more logarithmic factor
- Title not available (Why is that?)
- An improved algorithm for Boolean matrix multiplication
- Title not available (Why is that?)
- A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
- Probabilistic tensors and opportunistic Boolean matrix multiplication
- Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
- Efficiently correcting matrix products
- Title not available (Why is that?)
- Fast practical algorithms for the Boolean-product-witness-matrix problem
- A note on Boolean matrix multiplication
- Characteristic matrix of covering and its application to Boolean matrix decomposition
- Title not available (Why is that?)
- An improved bound on Boolean matrix multiplication for highly clustered data.
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- Fast Output-Sensitive 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)
