Matroid-reachability-based decomposition into arborescences
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929336291950592 |
|---|---|
| author | Hörsch, Florian Peyrille, Benjamin Szigeti, Zoltán |
| author_facet | Hörsch, Florian Peyrille, Benjamin Szigeti, Zoltán |
| contents | The problem of matroid-reachability-based packing of arborescences was solved by Király. Here we solve the corresponding decomposition problem that turns out to be more complicated. The result is obtained from the solution of the more general problem of matroid-reachability-based $(\ell,\ell')$-limited packing of arborescences where we are given a lower bound $\ell$ and an upper bound $\ell'$ on the total number of arborescences in the packing. The problem is considered for branchings and in directed hypergraphs as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03270 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matroid-reachability-based decomposition into arborescences Hörsch, Florian Peyrille, Benjamin Szigeti, Zoltán Combinatorics Discrete Mathematics 05C20 (Primary) 05B35, 05C20 (Secondary) The problem of matroid-reachability-based packing of arborescences was solved by Király. Here we solve the corresponding decomposition problem that turns out to be more complicated. The result is obtained from the solution of the more general problem of matroid-reachability-based $(\ell,\ell')$-limited packing of arborescences where we are given a lower bound $\ell$ and an upper bound $\ell'$ on the total number of arborescences in the packing. The problem is considered for branchings and in directed hypergraphs as well. |
| title | Matroid-reachability-based decomposition into arborescences |
| topic | Combinatorics Discrete Mathematics 05C20 (Primary) 05B35, 05C20 (Secondary) |
| url | https://arxiv.org/abs/2405.03270 |