3 citations · 11 across the 12 of their papers we have counts for
14 papers
Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
Georgios Stamoulis
In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with t…
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…
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…
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…
Integrality Gaps for Colorful Matchings
Steven Kelk, Georgios Stamoulis
We study the integrality gap of the natural linear programming relaxation for the \textit{Bounded Color Matching} (BCM) problem. We provide several families of instances and establ…
Treewidth distance on phylogenetic trees
Steven Kelk, Georgios Stamoulis, Taoyang Wu
In this article we study the treewidth of the \emph{display graph}, an auxiliary graph structure obtained from the fusion of phylogenetic (i.e., evolutionary) trees at their leaves…
A Structured View on Weighted Counting with Relations to Counting, Quantum Computation and Applications
Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland
Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path of polynomial-time non-deterministic Turing…
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 note on convex characters, Fibonacci numbers and exponential-time algorithms
Steven Kelk, Georgios Stamoulis
Phylogenetic trees are used to model evolution: leaves are labelled to represent contemporary species ("taxa") and interior vertices represent extinct ancestors. Informally, convex…
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…