A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor
Carla Groenland (TU Delft - Discrete Mathematics and Optimization)
Jesper Nederlof (Universiteit Utrecht)
Tomohiro Koana (Universiteit Utrecht)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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(n4) 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.
help_outline