We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in Oˆ(n3/log4n) time, where the Oˆ notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in Oˆ(n3/log3n) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the “easy parts” of a given instance efficiently, we can solve the whole problem faster than n3.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
- Boolean matrix multiplication
- Combinatorial algorithm