38 citations · 246 across the 68 of their papers we have counts for
8 papers · 1 filter
Complexity Framework For Forbidden Subgraphs I: The Framework
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen +4
For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. T…
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…
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…
Few Induced Disjoint Paths for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer , th…
Induced Disjoint Paths and Connected Subgraphs for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. The Induced Disjoint Paths…
The Complexity of Matching Games: A Survey
Márton Benedek, Péter Biró, Matthew Johnson +2
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 ne…