13 citations · 36 across the 16 of their papers we have counts for
29 papers
Dichotomies for Maximum Matching Cut: -Freeness, Bounded Diameter, Bounded Radius
Felicia Lucke, Daniël Paulusma, Bernard Ries
The (Perfect) Matching Cut problem is to decide if a graph has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of . Both Matching Cut and Perfe…
Matching Cuts in Graphs of High Girth and H-Free Graphs
Carl Feghali, Felicia Lucke, Daniel Paulusma +1
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a…
Finding Matching Cuts in -Free Graphs
Felicia Lucke, Daniël Paulusma, Bernard Ries
The 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…
Finding -community structures in special graph classes
Narmina Baghirova, Clément Dallard, Bernard Ries +1
For a fixed integer , a -community structure in an undirected graph is a partition of its vertex set into sets called communities, each of size at least two, such th…
On The Complexity of Matching Cut for Graphs of Bounded Radius and -Free Graphs
Felicia Lucke, Daniël Paulusma, Bernard Ries
For a connected graph , a matching is a matching cut of if is disconnected. It is known that for an integer , the corresponding decision proble…
Locally checkable problems parameterized by clique-width
Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries +1
We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on -locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph w…