Linear-algebraic implementation of Fibonacci heap - Demin, Danila; Sirotkin, Dmitry; Moiseev, Stanislav (Journal of Graph Algorithms and Applications, 2024)
In the paper, we demonstrate that modern priority queues can be expressed in terms of linear algebraic operations. Specifically, we showcase one of the arguably most asymptotically faster known priority queues — the Fibonacci heap. By employing our approach, we prove that for the Dijkstra, Prim, Brandes, and greedy maximal independent set algorithms, their theoretical complexity remains the same for both combinatorial and linear-algebraic cases.