A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
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_ | 1866912065087602688 |
|---|---|
| author | Groenland, Carla Nederlof, Jesper Koana, Tomohiro |
| author_facet | Groenland, Carla Nederlof, Jesper Koana, Tomohiro |
| contents | We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in $O(n^4)$ time, where $n$ denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06793 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor Groenland, Carla Nederlof, Jesper Koana, Tomohiro Data Structures and Algorithms We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in $O(n^4)$ time, where $n$ denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time. |
| title | A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.06793 |