Context-free path querying by matrix multiplication
Rustam Sadykovich Azimov, Semyon Grigorev · 2018
Context-free path querying is a technique, which recently gains popularity in many areas, for example, graph databases, bioinformatics, static analysis, etc. In some of these areas, it is often required to query large graphs, and existing algorithms demonstrate a poor performance in this case. The generalization of matrix-based Valiant's context-free language recognition algorithm for graph case is widely considered as a recipe for efficient context-free path querying; however, no progress has been made in this direction so far.