research
∙
04/03/2023
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
The (Perfect) Matching Cut problem is to decide if a graph G has a (perf...
share
research
∙
12/23/2022
Matching Cuts in Graphs of High Girth and H-Free Graphs
The (Perfect) Matching Cut is to decide if a graph has a (perfect) match...
research
∙
11/22/2022
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node ...
research
∙
02/23/2022
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Paths P_1,…, P_k in a graph G=(V,E) are mutually induced if any two dist...
research
∙
07/22/2016
