Geodesic
An efficient algorithm for finding final vertices in a generalized functional graph
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the 6th International Conference "Dynamic Systems and Computer Science: Theory and Applications" (DYSC 2024). Irkutsk, September 16-20, 2024. Part 1, Tome 238 (2025), pp. 59-68.

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

In the paper, 2-outgoing graphs are introduced into consideration, generalizing functional graphs and modeling discrete dynamic systems of a special type. The vertices and arcs of a 2-outgoing graph are classified, paths on these graphs are defined, and some properties of these paths are proved. As a result, an efficient algorithm is constructed that, with linear complexity, constructs final vertices for paths starting at each of the vertices of a 2-outgoing graph, and its correctness is proven.
Keywords: discrete dynamic system, functional graph, algorithm complexity 
@article{INTO_2025_238_a4,
     author = {O. V. Zubkov},
     title = {An efficient algorithm for finding final vertices in a generalized functional graph},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {59--68},
     publisher = {mathdoc},
     volume = {238},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2025_238_a4/}
}
TY  - JOUR
AU  - O. V. Zubkov
TI  - An efficient algorithm for finding final vertices in a generalized functional graph
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2025
SP  - 59
EP  - 68
VL  - 238
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2025_238_a4/
LA  - ru
ID  - INTO_2025_238_a4
ER  - 
%0 Journal Article
%A O. V. Zubkov
%T An efficient algorithm for finding final vertices in a generalized functional graph
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2025
%P 59-68
%V 238
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2025_238_a4/
%G ru
%F INTO_2025_238_a4
O. V. Zubkov. An efficient algorithm for finding final vertices in a generalized functional graph. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the 6th International Conference "Dynamic Systems and Computer Science: Theory and Applications" (DYSC 2024). Irkutsk, September 16-20, 2024. Part 1, Tome 238 (2025), pp. 59-68. http://geodesic.mathdoc.fr/item/INTO_2025_238_a4/

[1] Bykov I. C., “Funktsionirovanie diskretnoi dinamicheskoi sistemy tsirkulyantnogo tipa s porogovymi funktsiyami v vershinakh”, Prikl. diskr. mat., 26:4 (2014), 84–95 | Zbl

[2] Evdokimov A. A., Perezhogin A. L., “Diskretnye dinamicheskie sistemy tsirkulyantnogo tipa s lineinymi funktsiyami v vershinakh seti”, Diskr. anal. issled. oper., 18:3 (2011), 39–48 | Zbl

[3] Parfinenko A. C., Perezhogin A. L., “Funktsionalnyi graf lineinoi diskretnoi dinamicheskoi sistemy s dvumya dominiruyuschimi vershinami”, Diskr. anal. issled. oper., 25:4 (2018), 81–96 | MR | Zbl

[4] Harary F., “The number of functional digraphs”, Math. Ann., 139 (1959), 203–210 | DOI | MR