For a weighted digraph, an efficient algorithm is proposed for construction of minimum weight spanning forests with arbitrary number of trees, up to obtaining a minimum spanning tree if it exists. The algorithm consists in a succesively increasing in the number of arcs (decreasing the number of trees) while maintaining a certain degree of kinship 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 minimal spanning forests consisting of k trees for all admissible k. Its complexity does not exceed O(N3).

Original languageEnglish
Pages (from-to)117-129
Number of pages13
JournalJournal of Mathematical Sciences (United States)
Volume275
Issue number2
DOIs
StatePublished - 30 Sep 2023

    Scopus subject areas

  • Mathematics(all)

ID: 111446300