Steven Kelk

According to our database, Steven Kelk authored at least 79 papers between 2002 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Approximation ratio of the min-degree greedy algorithm for Maximum Independent Set on interval and chordal graphs.

Steven Chaplick, Martin Frohn, Steven Kelk, Johann Lottermoser, Matús Mihalák

Discret. Appl. Math., 2025

2024

Convex Characters, Algorithms, and Matchings.

Steven Kelk, Ruben Meuwese, Stephan Wagner

SIAM J. Discret. Math., March, 2024

Agreement forests of caterpillar trees: Complexity, kernelization and branching.

Steven Kelk, Ruben Meuwese

Theor. Comput. Sci., 2024

Deep kernelization for the Tree Bisection and Reconnection (TBR) distance in phylogenetics.

Steven Kelk, Simone Linz, Ruben Meuwese

J. Comput. Syst. Sci., 2024

A branch-&-price approach to the unrooted maximum agreement forest problem.

Martin Frohn, Steven Kelk, Simona Vychytilova

CoRR, 2024

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests.

David Mestel, Steven Chaplick, Steven Kelk, Ruben Meuwese

CoRR, 2024

Reconstructing semi-directed level-1 networks using few quarnets.

Martin Frohn, Niels Holtgrefe, Leo van Iersel, Mark Jones, Steven Kelk

CoRR, 2024

Relaxed Agreement Forests.

Virginia Ardévol Martínez, Steven Chaplick, Steven Kelk, Ruben Meuwese, Matús Mihalák, Georgios Stamoulis

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

2023

An improved kernel for the flip distance problem on simple convex polygons.

Miguel Bosch Calvo, Steven Kelk

Inf. Process. Lett., August, 2023

Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance.

Steven Kelk, Simone Linz, Ruben Meuwese

Inf. Process. Lett., 2023

Relaxed Agreement Forests.

Virginia Aardevol Martinez, Steven Chaplick, Steven Kelk, Ruben Meuwese, Matús Mihalák, Georgios Stamoulis

CoRR, 2023

Snakes and Ladders: A Treewidth Story.

Steven Chaplick, Steven Kelk, Ruben Meuwese, Matús Mihalák, Georgios Stamoulis

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

2022

Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics.

Steven Kelk, Simone Linz, Ruben Meuwese

CoRR, 2022

Sharp Upper and Lower Bounds on a Restricted Class of Convex Characters.

Steven Kelk, Ruben Meuwese

Electron. J. Comb., 2022

Reflections on kernelizing and computing unrooted agreement forests.

Rim van Wersch, Steven Kelk, Simone Linz, Georgios Stamoulis

Ann. Oper. Res., 2022

New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees.

Sander Borst, Leo van Iersel, Mark Jones, Steven Kelk

Algorithmica, 2022

2021

Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm.

Mark Jones, Steven Kelk, Leen Stougie

J. Comput. Syst. Sci., 2021

2020

Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm.

Mark Jones, Steven Kelk, Leen Stougie

CoRR, 2020

2019

A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees.

Steven Kelk, Simone Linz

SIAM J. Discret. Math., 2019

Treewidth of display graphs: bounds, brambles and applications.

Remie Janssen, Mark Jones, Steven Kelk, Georgios Stamoulis, Taoyang Wu

J. Graph Algorithms Appl., 2019

Integrality gaps for colorful matchings.

Steven Kelk, Georgios Stamoulis

Discret. Optim., 2019

Deciding the existence of a cherry-picking sequence is hard on two trees.

Janosch Döcker, Leo van Iersel, Steven Kelk, Simone Linz

Discret. Appl. Math., 2019

Cutting an alignment with Ockham's razor.

Mark Jones, Philippe Gambette, Leo van Iersel, Remie Janssen, Steven Kelk, Fabio Pardi, Céline Scornavacca

CoRR, 2019

Foundations of Digital Archæoludology.

Cameron Browne, Dennis J. N. J. Soemers, Éric Piette, Matthew Stephenson, Michael Conrad, Walter Crist, Thierry Depaulis, Eddie Duggan, Fred Horn, Steven Kelk, Simon M. Lucas, João Pedro Neto, David Parlett, Abdallah Saffidine, Ulrich Schädler, Jorge Nuno Silva, Alex de Voogt, Mark H. M. Winands

CoRR, 2019

New reduction rules for the tree bisection and reconnection distance.

Steven Kelk, Simone Linz

CoRR, 2019

Discovery of Important Subsequences in Electrocardiogram Beats Using the Nearest Neighbour Algorithm.

Ricards Marcinkevics, Steven Kelk, Carlo Galuzzi, Berthold Stegemann

CoRR, 2019

A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth.

Borislav Slavchev, Evelina Masliankova, Steven Kelk

Algorithms, 2019

2018

Treewidth distance on phylogenetic trees.

Steven Kelk, Georgios Stamoulis, Taoyang Wu

Theor. Comput. Sci., 2018

A third strike against perfect phylogeny.

Leo van Iersel, Mark Jones, Steven Kelk

CoRR, 2018

Integrality Gaps for Bounded Color Matchings.

Steven Kelk, Georgios Stamoulis

CoRR, 2018

On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems.

Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie, Olivier Boes

Algorithmica, 2018

On a Fixed Haplotype Variant of the Minimum Error Correction Problem.

Axel Goblet, Steven Kelk, Matús Mihalák, Georgios Stamoulis

Proceedings of the Computing and Combinatorics - 24th International Conference, 2018

2017

A Resolution of the Static Formulation Question for the Problem of Computing the History Bound.

Julia Matsieva, Steven Kelk, Céline Scornavacca, Chris Whidden, Dan Gusfield

IEEE ACM Trans. Comput. Biol. Bioinform., 2017

A Linear Bound on the Number of States in Optimal Convex Characters for Maximum Parsimony Distance.

Olivier Boes, Mareike Fischer, Steven Kelk

IEEE ACM Trans. Comput. Biol. Bioinform., 2017

ToTo: An open database for computation, storage and retrieval of tree decompositions.

Rim van Wersch, Steven Kelk

Discret. Appl. Math., 2017

Finding the most parsimonious or likely tree in a network with respect to an alignment.

Steven Kelk, Fabio Pardi, Céline Scornavacca, Leo van Iersel

CoRR, 2017

A note on convex characters, Fibonacci numbers and exponential-time algorithms.

Steven Kelk, Georgios Stamoulis

Adv. Appl. Math., 2017

Improving Card Fraud Detection Through Suspicious Pattern Discovery.

Fabian Braun, Olivier Caelen, Evgueni N. Smirnov, Steven Kelk, Bertrand Lebichot

Proceedings of the Advances in Artificial Intelligence: From Theory to Practice, 2017

2016

Reduction rules for the maximum parsimony distance on phylogenetic trees.

Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu

Theor. Comput. Sci., 2016

Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees.

Leo van Iersel, Steven Kelk, Nela Lekic, Simone Linz

Theor. Comput. Sci., 2016

Review of: Genome-Scale Algorithm Design (Biological sequence analysis in the era of high-throughput sequencing) by Veli Mäkinen, Djamal Belazzougui, Fabio Cunial and Alexandru I. Tomescu.

Steven Kelk

SIGACT News, 2016

Review of ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks by Dan Gusfield.

Steven Kelk

SIGACT News, 2016

Hybridization Number on Three Rooted Binary Trees is EPT.

Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden, Norbert Zeh

SIAM J. Discret. Math., 2016

Phylogenetic incongruence through the lens of Monadic Second Order logic.

Steven Kelk, Leo van Iersel, Céline Scornavacca, Mathias Weller

J. Graph Algorithms Appl., 2016

Kernelizations for the hybridization number problem on multiple nonbinary trees.

Leo van Iersel, Steven Kelk, Céline Scornavacca

J. Comput. Syst. Sci., 2016

Do branch lengths help to locate a tree in a phylogenetic network?

Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi, Céline Scornavacca

CoRR, 2016

2015

On Computing the Maximum Parsimony Score of a Phylogenetic Network.

Mareike Fischer, Leo van Iersel, Steven Kelk, Céline Scornavacca

SIAM J. Discret. Math., 2015

On Low Treewidth Graphs and Supertrees.

Alexander Grigoriev, Steven Kelk, Nela Lekic

J. Graph Algorithms Appl., 2015

Phylogenetic incongruence through the lens of Monadic Second Order logic.

Steven Kelk, Leo van Iersel, Céline Scornavacca

CoRR, 2015

A note on convex characters and Fibonacci numbers.

Steven Kelk

CoRR, 2015

2014

Approximation Algorithms for Nonbinary Agreement Forests.

Leo van Iersel, Steven Kelk, Nela Lekic, Leen Stougie

SIAM J. Discret. Math., 2014

The agreement problem for unrooted phylogenetic trees is FPT.

Céline Scornavacca, Leo van Iersel, Steven Kelk, David Bryant

J. Graph Algorithms Appl., 2014

On the complexity of computing MP distance between binary phylogenetic trees.

Steven Kelk, Mareike Fischer

CoRR, 2014

Hybridization Number on Three Trees.

Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden, Norbert Zeh

CoRR, 2014

A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees.

Leo van Iersel, Steven Kelk, Nela Lekic, Céline Scornavacca

BMC Bioinform., 2014

Constructing Minimal Phylogenetic Networks from Softwired Clusters is Fixed Parameter Tractable.

Steven Kelk, Céline Scornavacca

Algorithmica, 2014

Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees.

Leo van Iersel, Steven Kelk

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

2013

A Simple Fixed Parameter Tractable Algorithm for Computing the Hybridization Number of Two (Not Necessarily Binary) Trees.

Teresa Piovesan, Steven Kelk

IEEE ACM Trans. Comput. Biol. Bioinform., 2013

2012

On the Elusiveness of Clusters.

Steven Kelk, Céline Scornavacca, Leo van Iersel

IEEE ACM Trans. Comput. Biol. Bioinform., 2012

Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set.

Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Céline Scornavacca, Leen Stougie

SIAM J. Discret. Math., 2012

Computing nonbinary agreement forests

Leo van Iersel, Steven Kelk, Nela Lekic, Leen Stougie

CoRR, 2012

Towards the fixed parameter tractability of constructing minimal phylogenetic networks from arbitrary sets of nonbinary trees

Steven Kelk, Céline Scornavacca

CoRR, 2012

A Practical Approximation Algorithm for Solving Massive Instances of Hybridization Number.

Leo van Iersel, Steven Kelk, Nela Lekic, Céline Scornavacca

Proceedings of the Algorithms in Bioinformatics - 12th International Workshop, 2012

2011

A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks.

Katharina T. Huber, Leo van Iersel, Steven Kelk, Radoslaw Suchecki

IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Some Mathematical Refinements Concerning Error Minimization in the Genetic Code.

Harry Buhrman, Peter T. S. van der Gulik, Steven Kelk, Wouter M. Koolen, Leen Stougie

IEEE ACM Trans. Comput. Biol. Bioinform., 2011

A note on efficient computation of hybridization number via softwired clusters

Steven Kelk

CoRR, 2011

Constructing the Simplest Possible Phylogenetic Network from Triplets.

Leo van Iersel, Steven Kelk

Algorithmica, 2011

2010

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks.

Jaroslaw Byrka, Pawel Gawrychowski, Katharina T. Huber, Steven Kelk

J. Discrete Algorithms, 2010

Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters.

Leo van Iersel, Steven Kelk, Regula Rupp, Daniel H. Huson

Bioinform., 2010

2009

Constructing Level-2 Phylogenetic Networks from Triplets.

Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen, Teun Boekhout

IEEE ACM Trans. Comput. Biol. Bioinform., 2009

Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks.

Leo van Iersel, Steven Kelk, Matthias Mnich

J. Bioinform. Comput. Biol., 2009

2008

Shorelines of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems.

Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie

IEEE ACM Trans. Comput. Biol. Bioinform., 2008

2007

Prefix Reversals on Binary and Ternary Strings.

Cor A. J. Hurkens, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, John Tromp

SIAM J. Discret. Math., 2007

The Complexity of the Single Individual SNP Haplotyping Problem.

Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp

Algorithmica, 2007

2006

Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems.

Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie

Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

2005

On the Complexity of Several Haplotyping Problems.

Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp

Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

2004

The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random.

Leslie Ann Goldberg, Steven Kelk, Mike Paterson

SIAM J. Comput., 2004

2003

On the relative complexity of approximately counting H-colourings.

Steven M. Kelk

PhD thesis, 2003

2002

The complexity of choosing an H-colouring (nearly) uniformly at random.

Leslie Ann Goldberg, Steven Kelk, Mike Paterson

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002