Geodesic
Linear-algebraic implementation of Fibonacci heap
Danila Demin1 ; Dmitry Sirotkin2 ; Stanislav Moiseev2
1 Coleman Services
2 Huawei Technologies Co.
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 27-50.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.v28i1.2926
Keywords: linear-algebraic algorithms on graphs, Fibonacci heap, graph theory

Danila Demin 1 ; Dmitry Sirotkin 2 ; Stanislav Moiseev 2

1 Coleman Services
2 Huawei Technologies Co. 
@article{JGAA_2024_28_1_a1,
     author = {Danila Demin and Dmitry Sirotkin and Stanislav Moiseev},
     title = {Linear-algebraic implementation of {Fibonacci} heap},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {27--50},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2926},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2926/}
}
TY  - JOUR
AU  - Danila Demin
AU  - Dmitry Sirotkin
AU  - Stanislav Moiseev
TI  - Linear-algebraic implementation of Fibonacci heap
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 27
EP  - 50
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2926/
DO  - 10.7155/jgaa.v28i1.2926
LA  - en
ID  - JGAA_2024_28_1_a1
ER  - 
%0 Journal Article
%A Danila Demin
%A Dmitry Sirotkin
%A Stanislav Moiseev
%T Linear-algebraic implementation of Fibonacci heap
%J Journal of Graph Algorithms and Applications
%D 2024
%P 27-50
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2926/
%R 10.7155/jgaa.v28i1.2926
%G en
%F JGAA_2024_28_1_a1
Danila Demin; Dmitry Sirotkin; Stanislav Moiseev. Linear-algebraic implementation of Fibonacci heap. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 27-50. doi : 10.7155/jgaa.v28i1.2926. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2926/

Cité par Sources :