TY - GEN

T1 - An improved combinatorial algorithm for boolean matrix multiplication

AU - Yu, Huacheng

N1 - Funding Information:
H. Yu—Supported in part by NSF CCF-1212372.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in Ô(n3/ log4 n) time, where the Ô notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan [4] that runs in Ô (n3/ log3 n) 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.

AB - We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in Ô(n3/ log4 n) time, where the Ô notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan [4] that runs in Ô (n3/ log3 n) 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.

UR - http://www.scopus.com/inward/record.url?scp=84950125062&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950125062&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-47672-7_89

DO - 10.1007/978-3-662-47672-7_89

M3 - Conference contribution

AN - SCOPUS:84950125062

SN - 9783662476710

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1094

EP - 1105

BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings

A2 - Halldorsson, Magnus M.

A2 - Kobayashi, Naoki

A2 - Speckmann, Bettina

A2 - Iwama, Kazuo

PB - Springer Verlag

T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

Y2 - 6 July 2015 through 10 July 2015

ER -