Linear-algebraic implementation of Fibonacci heap

Authors

  • Danila Demin Coleman Services
  • Dmitry Sirotkin Huawei Technologies Co.
  • Stanislav Moiseev Huawei Technologies Co.

DOI:

https://doi.org/10.7155/jgaa.v28i1.2926

Keywords:

linear-algebraic algorithms on graphs, Fibonacci heap, graph theory

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2024-05-16

How to Cite

Demin, D., Sirotkin, D., & Moiseev, S. (2024). Linear-algebraic implementation of Fibonacci heap. Journal of Graph Algorithms and Applications, 28(1), 27–50. https://doi.org/10.7155/jgaa.v28i1.2926

Issue

Section

Articles

Categories