Matroid reinforcement and sparsification
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_ | 1866909275949891584 |
|---|---|
| author | Truong, Huy Poggi-Corradini, Pietro |
| author_facet | Truong, Huy Poggi-Corradini, Pietro |
| contents | Homogeneous matroids are characterized by the property that strength equals fractional arboricity, and arise in the study of base modulus [22]. For graphic matroids, Cunningham [9] provided efficient algorithms for calculating graph strength, and also for determining minimum cost reinforcement to achieve a desired strength. This paper extends this latter problem by focusing on two optimal strategies for transforming a matroid into a homogeneous one, by either increasing or decreasing element weights. As an application to graphs, we give algorithms to solve this problem in the context of spanning trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00173 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matroid reinforcement and sparsification Truong, Huy Poggi-Corradini, Pietro Combinatorics 05C85 (Primary), 90C27 (Secondary) Homogeneous matroids are characterized by the property that strength equals fractional arboricity, and arise in the study of base modulus [22]. For graphic matroids, Cunningham [9] provided efficient algorithms for calculating graph strength, and also for determining minimum cost reinforcement to achieve a desired strength. This paper extends this latter problem by focusing on two optimal strategies for transforming a matroid into a homogeneous one, by either increasing or decreasing element weights. As an application to graphs, we give algorithms to solve this problem in the context of spanning trees. |
| title | Matroid reinforcement and sparsification |
| topic | Combinatorics 05C85 (Primary), 90C27 (Secondary) |
| url | https://arxiv.org/abs/2408.00173 |