3 citations · 11 across the 12 of their papers we have counts for
8 papers · 1 filter
Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching
Georgios Stamoulis
We study the rainbow matching (RM) problem: given an edge-colored graph, find a maximum matching with at most one edge of each color. Rainbow matchings correspond to stable sets in…
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…
Reflections on kernelizing and computing unrooted agreement forests
Rim van Wersch, Steven Kelk, Simone Linz +1
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard proble…
Treewidth of display graphs: bounds, brambles and applications
Remie Janssen, Mark Jones, Steven Kelk +2
Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or…
PTAS for Ordered Instances of Resource Allocation Problems with Restrictions on Inclusions
Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey +1
We consider the problem of allocating a set of indivisible resources (items) to a set of customers (players) competing for the resources. Each resource ha…
On unrooted and root-uncertain variants of several well-known phylogenetic network problems
Leo van Iersel, Steven Kelk, Georgios Stamoulis +2
The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegre…
A 0.821-ratio purely combinatorial algorithm for maximum -vertex cover in bipartite graphs
Edouard Bonnet, Bruno Escoffier, Vangelis Paschos +1
Our goal in this paper is to propose a \textit{combinatorial algorithm} that beats the only such algorithm known previously, the greedy one. We study the polynomial approximation o…
Bi-Criteria and Approximation Algorithms for Restricted Matchings
Monaldo Mastrolilli, Georgios Stamoulis
In this work we study approximation algorithms for the \textit{Bounded Color Matching} problem (a.k.a. Restricted Matching problem) which is defined as follows: given a graph in wh…