Geodesic
Algorithm for sequential construction of spanning minimal directed forests
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XII, Tome 497 (2020), pp. 5-25 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

For a weighted digraph, an efficient algorithm for constructing spanning forests of the minimum weight for an arbitrary number of trees is proposed, up to obtaining the minimum spanning tree, if it exists. Algorithm consists in a sequential increase in the number of arcs (decrease in the number of trees) while maintaining a certain degree of affinity between minimal forests when the number of trees changes. The correctness of the algorithm is proved and its complexity is determined. The result of the algorithm is a set of minimum spanning forests consisting of $k$ trees for all admissible $k$. Its complexity does not exceed $O(N^3)$. 
@article{ZNSL_2020_497_a0,
     author = {V. A. Buslov},
     title = {Algorithm for sequential construction of spanning minimal directed forests},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {5--25},
     year = {2020},
     volume = {497},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2020_497_a0/}
}
TY  - JOUR
AU  - V. A. Buslov
TI  - Algorithm for sequential construction of spanning minimal directed forests
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2020
SP  - 5
EP  - 25
VL  - 497
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2020_497_a0/
LA  - ru
ID  - ZNSL_2020_497_a0
ER  - 
%0 Journal Article
%A V. A. Buslov
%T Algorithm for sequential construction of spanning minimal directed forests
%J Zapiski Nauchnykh Seminarov POMI
%D 2020
%P 5-25
%V 497
%U http://geodesic.mathdoc.fr/item/ZNSL_2020_497_a0/
%G ru
%F ZNSL_2020_497_a0
V. A. Buslov. Algorithm for sequential construction of spanning minimal directed forests. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XII, Tome 497 (2020), pp. 5-25. http://geodesic.mathdoc.fr/item/ZNSL_2020_497_a0/

[1] V. A. Buslov, “Struktura orientirovannykh lesov minimalnogo vesa: rodstvennye lesa i neravenstva vypuklosti”, Zap. nauchn. sem. POMI, 475, 2018, 5–21

[2] R. C. Prim, “Shortest connection networks and some generalizations”, Bell System Techn. J., 36 (1957), 1389–1401 | DOI

[3] Joseph. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proc. AMS, 7:1 (1956), 48–50 | DOI | MR | Zbl

[4] Y. J. Chu, T. H. Liu, “On the shortest arborescence of a directed graph”, Sci. Sinica, 14 (1965), 1396–1400 | MR | Zbl

[5] J. Edmonds, “Optimum branchings”, J. Res. Nat. Bur. Standards, 71:B (1967), 233–240 | DOI | MR | Zbl

[6] R. E. Tarjan, “Finding optimum branchings”, Networks, 7:1 (1977) | DOI | MR | Zbl

[7] H. N. Gabov, Z. Galil, T. Spencer, R. E. Tarjan, “Efficient Algorithms for Finding Minimum Spanning Trees in Undirecrted and Directed Graphs”, Combinatorica, 6:2 (1986), 109–122 | DOI | MR

[8] V. A. Buslov, “Struktura orientirovannykh lesov minimalnogo vesa: algebry podmnozhestv mnozhestva vershin”, Zap. nauchn. sem. POMI, 488, 2019, 5–30 | MR

[9] V. A. Buslov, “O koeffitsientakh kharakteristicheskogo mnogochlena laplasiana vzveshennogo orientirovannogo grafa i teoreme o vsekh minorakh”, Zap. nauchn. sem. POMI, 427, 2014, 5–21

[10] V. A. Buslov, “O kharakteristicheskom mnogochlene i sobstvennykh vektorakh v terminakh drevovidnoi struktury orgrafa”, Zap. nauchn. sem. POMI, 450, 2016, 14–36

[11] V. A. Buslov, “O svyazi kratnostei spektra so znakami slagaemykh v komponentakh sobstvennykh vektorov v drevovidnoi strukture”, Zap. nauchn. sem. POMI, 464, 2017, 14–36

[12] V. A. Buslov, K. A. Makarov, “Ierarkhiya masshtabov vremeni pri maloi diffuzii”, TMF, 76:2 (1988), 219–230 | MR | Zbl

[13] V. A. Buslov, K. A. Makarov, “Vremena zhizni i nizshie sobstvennye znacheniya operatora maloi diffuzii”, Mat. zametki, 51:1 (1992), 20–31 | MR | Zbl

[14] A. D. Venttsel, M. I. Freidlin, Fluktuatsii v dinamicheskikh sistemakh pod deistviem malykh sluchainykh vozmuschenii, M., 1979, 429 pp.

[15] A. D. Venttsel, “Ob asimptotike sobstvennykh znachenii matrits s elementami poryadka $\exp\{-V_{ij}/2\varepsilon^2\}$”, DAN SSSR, 202:2 (1972), 263–266 | MR