25 citations · 79 across the 15 of their papers we have counts for
31 papers
Finding -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
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…
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Matthew Johnson, Barnaby Martin, Sukanya Pandey +3
For any finite set of graphs, a graph is -subgraph-free if it does not contain any of as a subgraph. In recent work…
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…
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…
Computing Weighted Subset Transversals in -Free Graphs
Nick Brettell, Matthew Johnson, Daniel Paulusma
For the Odd Cycle Transversal problem, the task is to find a small set of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal proble…