Geodesic
Combinatorial algorithm for finding the number of paths on a directed graph
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh spring mathematical school "Modern methods of the theory of boundary-value problems. Pontryagin readings – XXXI". Voronezh, May 3-9, 2020, Tome 204 (2022), pp. 37-43

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we present an algorithm for finding the number of paths on a directed graph that start at an arbitrary subset of its vertices. The algorithm is based on the ideas underlying the construction of Pascal's triangle. The complexity of the algorithm coincides with the complexity of the well-known Dijkstra algorithm for finding shortest paths on graphs. We also generalize the algorithm proposed to the problem on graphs with reachability constraints.
Keywords: directed graph, path, reachability constraints.
Mots-clés : Pascal's triangle 
@article{INTO_2022_204_a3,
     author = {I. M. Erusalimskyi and M. I. Cherdyntseva},
     title = {Combinatorial algorithm for finding the number of paths on a directed graph},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {37--43},
     publisher = {mathdoc},
     volume = {204},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2022_204_a3/}
}
TY  - JOUR
AU  - I. M. Erusalimskyi
AU  - M. I. Cherdyntseva
TI  - Combinatorial algorithm for finding the number of paths on a directed graph
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2022
SP  - 37
EP  - 43
VL  - 204
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2022_204_a3/
LA  - ru
ID  - INTO_2022_204_a3
ER  - 
%0 Journal Article
%A I. M. Erusalimskyi
%A M. I. Cherdyntseva
%T Combinatorial algorithm for finding the number of paths on a directed graph
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2022
%P 37-43
%V 204
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2022_204_a3/
%G ru
%F INTO_2022_204_a3
I. M. Erusalimskyi; M. I. Cherdyntseva. Combinatorial algorithm for finding the number of paths on a directed graph. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh spring mathematical school "Modern methods of the theory of boundary-value problems. Pontryagin readings – XXXI". Voronezh, May 3-9, 2020, Tome 204 (2022), pp. 37-43. http://geodesic.mathdoc.fr/item/INTO_2022_204_a3/