Spanning Trees Minimizing Branching Costs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909689590054912 |
|---|---|
| author | Gargano, Luisa Rescigno, Adele A. |
| author_facet | Gargano, Luisa Rescigno, Adele A. |
| contents | The Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$. This problem, known to be NP-hard, has attracted significant attention due to its importance in network design and optimization. Extensive research has been conducted on the algorithmic and combinatorial aspects of this problem, with recent studies delving into its fixed-parameter tractability.
In this paper, we focus primarily on the parameter modular-width. We demonstrate that finding a spanning tree with the minimum number of branch vertices is Fixed-Parameter Tractable (FPT) when considered with respect to modular-width. Additionally, in cases where each vertex in the input graph has an associated cost for serving as a branch vertex, we prove that the problem of finding a spanning tree with the minimum branch cost (i.e., minimizing the sum of the costs of branch vertices) is FPT with respect to neighborhood diversity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10571 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spanning Trees Minimizing Branching Costs Gargano, Luisa Rescigno, Adele A. Data Structures and Algorithms Computational Complexity F.2.2 The Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$. This problem, known to be NP-hard, has attracted significant attention due to its importance in network design and optimization. Extensive research has been conducted on the algorithmic and combinatorial aspects of this problem, with recent studies delving into its fixed-parameter tractability. In this paper, we focus primarily on the parameter modular-width. We demonstrate that finding a spanning tree with the minimum number of branch vertices is Fixed-Parameter Tractable (FPT) when considered with respect to modular-width. Additionally, in cases where each vertex in the input graph has an associated cost for serving as a branch vertex, we prove that the problem of finding a spanning tree with the minimum branch cost (i.e., minimizing the sum of the costs of branch vertices) is FPT with respect to neighborhood diversity. |
| title | Spanning Trees Minimizing Branching Costs |
| topic | Data Structures and Algorithms Computational Complexity F.2.2 |
| url | https://arxiv.org/abs/2407.10571 |