Witnesses for Boolean matrix multiplication and for transitive closure

DOI10.1006/jcom.1993.1014zbMath0785.65053OpenAlexW1965216219MaRDI QIDQ1260654

Olded Margalit, Zvi Galil

Publication date: 24 August 1993

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1993.1014

zbMATH Keywords

time complexitytransitive closuredeterministic algorithmBoolean matrix multiplicationmatrix of witnessesshortest paths problem

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrices of integers (15B36)

Related Items (5)

Faster algorithms for finding lowest common ancestors in directed acyclic graphs ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Path Laplacian matrices: introduction and application to the analysis of consensus in networks ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ On minimum witnesses for Boolean matrix multiplication

This page was built for publication: Witnesses for Boolean matrix multiplication and for transitive closure