A fast output-sensitive algorithm for Boolean matrix multiplication
From MaRDI portal
Publication:634680
DOI10.1007/s00453-010-9441-xzbMath1218.68195OpenAlexW2141293105MaRDI QIDQ634680
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
time complexityBoolean matrix multiplicationoutput-sensitive algorithmrectangular matrix multiplication
Related Items (5)
Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Efficiently correcting matrix products ⋮ Characteristic matrix of covering and its application to Boolean matrix decomposition ⋮ Better size estimation for sparse matrix products ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- On the power of two-point based sampling
- Complexity of monotone networks for Boolean matrix product
- Fast rectangular matrix multiplication and applications
- Structure prediction and computation of sparse matrix products
- Rectangular matrix multiplication revisited
- On a set of almost deterministic k-independent random variables
- Min-wise independent permutations
- PRIMES is in P
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Efficient determination of the transitive closure of a directed graph
- Fast recognition of pushdown automaton and context-free languages
- The Power of Negative Thinking in Multiplying Boolean Matrices
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Algorithms – ESA 2004
- Automata, Languages and Programming
This page was built for publication: A fast output-sensitive algorithm for Boolean matrix multiplication
