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/

[1] Basangova E. O., Erusalimskii Ya. M., “Razlichnye vidy smeshannoi dostizhimosti”, Algebra i diskretnaya matematika, KalmGU, Elista, 1985, 70–75 | MR

[2] Basangova E. O., Erusalimskii Ya. M., “Smeshannaya dostizhimost na chastichno orientirovannykh grafakh”, Vychislitelnye sistemy i algoritmy, RGU, Rostov-na-Donu, 1983, 135–140

[3] Erusalimskii Ya. M., “2–3 puti na grafe-reshetke. Sluchainye bluzhdaniya”, Mat. zametki., 104:3 (2018), 396–406 | MR | Zbl

[4] Erusalimskii Ya. M., Diskretnaya matematika. Teoriya i praktikum, Lan, SPb., 2018

[5] Erusalimskii Ya. M., Treugolnik Paskalya: kombinatorika i sluchainye bluzhdaniya, Vuzovskaya kniga, M., 2020

[6] Erusalimskii Ya. M., Petrosyan A. G., “Mnogoproduktovye potoki v setyakh s nestandartnoi dostizhimostyu”, Izv. vuzov. Sev.-Kav. reg. Estestv. nauki. Prilozh., 2005, no. 6, 8–16

[7] Erusalimskii Ya. M., Skorokhodov V. A., “Obschii podkhod k nestandartnoi dostizhimosti na grafakh”, Izv. vuzov. Sev.-Kav. reg. Estestv. nauki., Spetsvypusk. Psevdodifferentsialnye uravneniya i nekotorye problemy matematicheskoi fiziki (2005), 64–67

[8] Erusalimskii Ya. M., Skorokhodov V. A., “O potokakh v seti s ogranicheniyami na dostizhimost. Vychislitelnyi eksperiment”, Mat. Vesennei Voronezh. mat. shkoly «Sovremennye metody teorii kraevykh zadach» (Pontryaginskie chteniya–KhKhVI), Voronezh, 2015, 89–90

[9] Erusalimskii Ya. M., Skorokhodov V. A., “Potoki v setyakh so svyazannymi dugami”, Izv. vuzov. Sev.-Kav. reg. Estestv. nauki. Prilozh., 2003, no. 8, 9–12 | Zbl

[10] Erusalimskii Ya. M., Skorokhodov V. A., “Pribyl ot potokov s obratnoi svyazyu v orsetyakh s ogranicheniyami na dostizhimost”, Izv. vuzov. Sev.-Kav. reg. Estestv. nauki. Prilozh., 2003, no. 8, 3–8 | Zbl

[11] Erusalimskii Ya. M., Skorokhodov V. A., Kuzminova M. V., Petrosyan A. G., Grafy s nestandartnoi dostizhimostyu. Zadachi, prilozheniya, YuFU, Rostov-na-Donu, 2009

[12] Zhilyakova L. Yu., “Grafovye dinamicheskie modeli i ikh svoistva”, Avtomat. telemekh., 8 (2015), 115–139 | MR | Zbl

[13] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numer. Math., 1 (1959), 269–271 | DOI | MR | Zbl

[14] Erusalimskiy I. M., “Graph–lattice: random walk and combinatorial identities”, Bol. Soc. Mat. Mexicana., 22:2 (2016), 329–335 | DOI | MR | Zbl