Department of Computer Science

Solving problems on generalized convex graphs via mim-width (2023)
Journal Article
Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2024). Solving problems on generalized convex graphs via mim-width. Journal of Computer and System Sciences, 140, Article 103493. https://doi.org/10.1016/j.jcss.2023.103493

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.

Excluded minors are almost fragile (2020)
Journal Article
Brettell, N., Clark, B., Oxley, J., Semple, C., & Whittle, G. (2020). Excluded minors are almost fragile. Journal of Combinatorial Theory, Series B, 140, 263-322. https://doi.org/10.1016/j.jctb.2019.05.008

N-detachable pairs in 3-connected matroids I: Unveiling X (2019)
Journal Article
Brettell, N., Whittle, G., & Williams, A. (2020). N-detachable pairs in 3-connected matroids I: Unveiling X. Journal of Combinatorial Theory, Series B, 141, 295-342. https://doi.org/10.1016/j.jctb.2019.08.005

Let M be a 3-connected matroid, and let N be a 3-connected minor of M. We say that a pair is N-detachable if one of the matroids or is both 3-connected and has an N-minor. This is the first in a series of three papers where we describe the structures... Read More about N-detachable pairs in 3-connected matroids I: Unveiling X.

Coloring Graphs with Constraints on Connectivity (2016)
Journal Article
Aboulker, P., Brettell, N., Havet, F., Marx, D., & Trotignon, N. (2016). Coloring Graphs with Constraints on Connectivity. Journal of Graph Theory, 85(4), 814-838. https://doi.org/10.1002/jgt.22109

A graph G has maximal local edge‐connectivity k if the maximum number of edge‐disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks‐type theorems for k‐connected graphs with maximal local edge‐connectivity k, an... Read More about Coloring Graphs with Constraints on Connectivity.

Outputs (6)