4 papers · 1 filter
Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
Felicia Lucke, Ali Momeni, Daniël Paulusma +1
The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If , we obtain the intensively studie…
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…