Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
From MaRDI portal
Publication:6179437
DOI10.1007/978-3-031-38906-1_33OpenAlexW4385317265MaRDI QIDQ6179437
Meng-Tsung Tsai, Hung-Lung Wang, Wing-Kai Hon
Publication date: 16 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-38906-1_33
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- A note on alternating cycles in edge-coloured graphs
- A simple linear time algorithm for cograph recognition
- Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
- Efficiently correcting matrix products
- Gaussian elimination is not optimal
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A Linear Recognition Algorithm for Cographs
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Finding Even Cycles Even Faster
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Exact Perfect Matching in Complete Graphs
- Error Correction in Fast Matrix Multiplication and Inverse
- LU Factorization with Errors
- Quadratic-time certificates in linear algebra
- Finding Four-Node Subgraphs in Triangle Time
- Difference graphs
- Edge‐colored complete graphs without properly colored even cycles: A full characterization
