Algorithm for Sequential Construction of Spanning Minimal Directed Forests

Standard

Algorithm for Sequential Construction of Spanning Minimal Directed Forests. / Буслов, Василий Анатольевич.

In: Journal of Mathematical Sciences (United States), Vol. 275, No. 2, 30.09.2023, p. 117-129.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{eaf5d846685944a695d67642ef2739ec,

title = "Algorithm for Sequential Construction of Spanning Minimal Directed Forests",

abstract = "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).",

keywords = "weighted digraph, spanning subgraph, minimal forest",

author = "Буслов, {Василий Анатольевич}",

year = "2023",

month = sep,

day = "30",

doi = "10.1007/s10958-023-06666-w",

language = "English",

volume = "275",

pages = "117--129",

journal = "Journal of Mathematical Sciences",

issn = "1072-3374",

publisher = "Springer Nature",

number = "2",

}

RIS

TY - JOUR

T1 - Algorithm for Sequential Construction of Spanning Minimal Directed Forests

AU - Буслов, Василий Анатольевич

PY - 2023/9/30

Y1 - 2023/9/30

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

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

KW - weighted digraph, spanning subgraph, minimal forest

UR - https://www.mendeley.com/catalogue/bd9f6414-45b6-3de8-90e3-bb65fb6f1b37/

U2 - 10.1007/s10958-023-06666-w

DO - 10.1007/s10958-023-06666-w

M3 - Article

VL - 275

SP - 117

EP - 129

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 2

ER -

ID: 111446300