Outputs (311)

Partitioned matching games for international kidney exchange (2025)
Journal Article
Benedek, M., Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (online). Partitioned matching games for international kidney exchange. Mathematical Programming, https://doi.org/10.1007/s10107-025-02200-9

Computing subset vertex covers in H-free graphs (2025)
Journal Article
Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., Rauch, J., & van Leeuwen, E. J. (2025). Computing subset vertex covers in H-free graphs. Theoretical Computer Science, 1032, Article 115088. https://doi.org/10.1016/j.tcs.2025.115088

Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs, (2025)
Presentation / Conference Contribution
Lucke, F., Momeni, A., Paulusma, D., & Smith, S. (2024, June). Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,. Presented at WG 2024, Gozd Martuljek, Slovenia

The Complexity of Diameter on H-free Graphs (2025)
Presentation / Conference Contribution
Oostveen, J. J., Paulusma, D., & van Leeuwen, E. J. (2024, June). The Complexity of Diameter on H-free Graphs. Presented at WG 2024, Gozd Martuljek, Slovenia

Complexity Framework for Forbidden Subgraphs I: The Framework (2025)
Journal Article
Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2

For a set of graphs H, a graph G is H-subgraph-free if G does not contain any graph from H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for H-subgraph-free graphs. Namely, a grap... Read More about Complexity Framework for Forbidden Subgraphs I: The Framework.

Maximizing Matching Cuts (2024)
Book Chapter
Le, V. B., Lucke, F., Paulusma, D., & Ries, B. (2024). Maximizing Matching Cuts. In P. M. Pardalos, & O. A. Prokopyev (Eds.), Encyclopedia of Optimization (1-10). Springer Nature. https://doi.org/10.1007/978-3-030-54621-2_898-1

Graph cut problems belong to a well-studied class of classical graph problems related to network connectivity, which is a central concept within theoretical computer science.

Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs (2024)
Presentation / Conference Contribution
Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024

For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are... Read More about Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs.

Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius (2024)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2024). Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius. Theoretical Computer Science, 1017, Article 114795. https://doi.org/10.1016/j.tcs.2024.114795

Complexity framework for forbidden subgraphs IV: The Steiner Forest problem (2024)
Presentation / Conference Contribution
Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, July). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Presented at IWOCA, Ischia, Italy

Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs (2024)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland

It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degr... Read More about Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs.