37 citations · 112 across the 33 of their papers we have counts for
50 papers
A Note on the Complexity of Defensive Domination
Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk
In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to…
Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
David Mestel, Steven Chaplick, Steven Kelk +1
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. In practice it is not uncommon to obtain two topologically distinct trees for the same set of spe…
Monotone Arc Diagrams with few Biarcs
Steven Chaplick, Henry Förster, Michael Hoffmann +1
We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spi…
Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
Steven Chaplick, Martin Frohn, Steven Kelk +2
In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a -approximation for the Maximum Independent Set problem on interval gra…
Relaxed Agreement Forests
Virginia Aardevol Martinez, Steven Chaplick, Steven Kelk +3
There are multiple factors which can cause the phylogenetic inference process to produce two or more conflicting hypotheses of the evolutionary history of a set X of biological ent…
Snakes and Ladders: a Treewidth Story
Steven Chaplick, Steven Kelk, Ruben Meuwese +2
Let be an undirected graph. We say that contains a ladder of length if the grid graph is an induced subgraph of that is only connected to the rest…