2 citations · 4 across the 10 of their papers we have counts for
3 papers · 2 filters
Maximizing Matching Cuts
Van Bang Le, Felicia Lucke, Daniël Paulusma +1
A matching cut in a graph G is an edge cut of G that is also a matching. This short survey gives an overview of old and new results and open problems for Maximum Matching Cut, whic…
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin +5
We study Steiner Forest on -subgraph-free graphs, that is, graphs that do not contain some fixed graph as a (not necessarily induced) subgraph. We are motivated by a recent…
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…