TY - GEN
T1 - An improved combinatorial algorithm for boolean matrix multiplication
AU - Yu, Huacheng
N1 - 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 -