Skip to main content

Research Repository

Advanced Search

Outputs (11)

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

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius (2023)
Presentation / Conference Contribution
Lucke, F., Paulusma, D., & Ries, B. (2023, August). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity re... Read More about Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

The Complexity of Matching Games: A Survey (2023)
Journal Article
Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of m... Read More about The Complexity of Matching Games: A Survey.

Finding Matching Cuts in H-Free Graphs (2023)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, 85(10), 3290-3322. https://doi.org/10.1007/s00453-023-01137-9

The well-known NP-complete problem MATCHING CUT is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for MATCHING CUT restricted to H-free graphs, that is, graphs that do not contain some fixed... Read More about Finding Matching Cuts in H-Free Graphs.

The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4

The L(p, q)-EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p, q)-Edge-Labelling.