Algorithm for Constructing Related Spanning Directed Forests of Minimum Weight
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915153794039808 |
|---|---|
| author | Buslov, Vasily |
| author_facet | Buslov, Vasily |
| contents | An algorithm is proposed for constructing directed spanning forests of the minimum weight, in which the maximum possible degree of affinity between the minimum forests is preserved when the number of trees changes. The correctness of the algorithm is checked and its complexity is determined, which does not exceed $ O (N ^ 3) $ for dense graphs. The result of the algorithm is a set of related spanning minimal forests consisting of $ k $ trees for all admissible $ k $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05946 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithm for Constructing Related Spanning Directed Forests of Minimum Weight Buslov, Vasily Combinatorics 05C20 (Primary) 05C35 (Secondary) G.2.2 An algorithm is proposed for constructing directed spanning forests of the minimum weight, in which the maximum possible degree of affinity between the minimum forests is preserved when the number of trees changes. The correctness of the algorithm is checked and its complexity is determined, which does not exceed $ O (N ^ 3) $ for dense graphs. The result of the algorithm is a set of related spanning minimal forests consisting of $ k $ trees for all admissible $ k $. |
| title | Algorithm for Constructing Related Spanning Directed Forests of Minimum Weight |
| topic | Combinatorics 05C20 (Primary) 05C35 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2502.05946 |