The Minimum Weighting Ratio Problem and Its Application in Chordal Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929648459317248 |
|---|---|
| author | Lei, Hui Lu, Mei Shi, Yongtang Sun, Jian Zhao, Xiamiao |
| author_facet | Lei, Hui Lu, Mei Shi, Yongtang Sun, Jian Zhao, Xiamiao |
| contents | Constructing the maximum spanning tree $T$ of an edge-weighted connected graph $G$ is one of the important research topics in computer science and optimization, and the related research results have played an active role in practical applications. In this paper, we are concerned with the ratio of the weighted sum of a spanning tree $T$ of $G$ to the weighted sum of $G$, which we try to minimize. We propose an interesting theorem to simplify this problem and show that this optimal problem can be solved in polynomial time. Furthermore, we apply the optimal problem in chordal graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18861 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Minimum Weighting Ratio Problem and Its Application in Chordal Graphs Lei, Hui Lu, Mei Shi, Yongtang Sun, Jian Zhao, Xiamiao Combinatorics Constructing the maximum spanning tree $T$ of an edge-weighted connected graph $G$ is one of the important research topics in computer science and optimization, and the related research results have played an active role in practical applications. In this paper, we are concerned with the ratio of the weighted sum of a spanning tree $T$ of $G$ to the weighted sum of $G$, which we try to minimize. We propose an interesting theorem to simplify this problem and show that this optimal problem can be solved in polynomial time. Furthermore, we apply the optimal problem in chordal graphs. |
| title | The Minimum Weighting Ratio Problem and Its Application in Chordal Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.18861 |