Steiner trees for hereditary graph classes

Bodlaender, H.; Brettell, N.; Johnson, M.; Paesani, G.; Paulusma, D.; van Leeuwen, E. J.

doi:10.1007/978-3-030-61792-9_48

All Outputs (2)

Computing Subset Vertex Covers in H-Free Graphs (2023)
Presentation / Conference Contribution
Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., & van Leeuwen, E. J. (2023, September). Computing Subset Vertex Covers in H-Free Graphs. Presented at FCT 2023: Fundamentals of Computation Theory, Trier, Germany

Steiner trees for hereditary graph classes (2020)
Presentation / Conference Contribution
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (... Read More about Steiner trees for hereditary graph classes.