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

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

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},
     publisher = {mathdoc},
     volume = {497},
     year = {2020},
     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
PB  - mathdoc
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
%I mathdoc
%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/