DOI

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).

Язык оригиналаанглийский
Страницы (с-по)117-129
Число страниц13
ЖурналJournal of Mathematical Sciences (United States)
Том275
Номер выпуска2
DOI
СостояниеОпубликовано - 30 сен 2023

    Области исследований

  • weighted digraph, spanning subgraph, minimal forest

    Предметные области Scopus

  • Математика (все)

ID: 111446300