3 papers
cs.DS2024
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…
cs.DS2023
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…
cs.GT2014
An Upper Bound on the Price of Stability of Undirected Network Design Games
Akaki Mamageishvili, Matúš Mihalák, Simone Montemezzani
In the network design game with players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all…