2 citations · 4 across the 5 of their papers we have counts for
3 papers · 1 filter
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…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…