Minimal $L^p$-congestion spanning trees on weighted graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908356229201920 |
|---|---|
| author | Lafuente, Alberto Castejón Estévez, Emilio Cotón, Carlos Meniño Somoza, M. Carmen |
| author_facet | Lafuente, Alberto Castejón Estévez, Emilio Cotón, Carlos Meniño Somoza, M. Carmen |
| contents | A generalization of the notion of spanning tree congestion for weighted graphs is introduced. The $L^p$ congestion of a spanning tree is defined as the $L^p$ norm of the edge congestion of that tree. In this context, the classical congestion is the $L^\infty$-congestion. Explicit estimations of the minimal spanning tree $L^p$ congestion for some families of graphs are given. In addition, we introduce a polynomial-time algorithm for approximating the minimal $L^p$-congestion spanning tree in any weighted graph and another two similar algorithms for weighted planar graphs. The performance of these algorithms is tested in several graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05969 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimal $L^p$-congestion spanning trees on weighted graphs Lafuente, Alberto Castejón Estévez, Emilio Cotón, Carlos Meniño Somoza, M. Carmen Discrete Mathematics Combinatorics 05C22, 05C85, 90C59 A generalization of the notion of spanning tree congestion for weighted graphs is introduced. The $L^p$ congestion of a spanning tree is defined as the $L^p$ norm of the edge congestion of that tree. In this context, the classical congestion is the $L^\infty$-congestion. Explicit estimations of the minimal spanning tree $L^p$ congestion for some families of graphs are given. In addition, we introduce a polynomial-time algorithm for approximating the minimal $L^p$-congestion spanning tree in any weighted graph and another two similar algorithms for weighted planar graphs. The performance of these algorithms is tested in several graphs. |
| title | Minimal $L^p$-congestion spanning trees on weighted graphs |
| topic | Discrete Mathematics Combinatorics 05C22, 05C85, 90C59 |
| url | https://arxiv.org/abs/2505.05969 |