Publications (71)
Cryptographic Enforcement of Information Flow Policies without Public Information
Jason Crampton, Naomi Farley, Gregory Gutin +2
Cryptographic access control has been studied for over 30 years and is now a mature research topic. When symmetric cryptographic primitives are used, each protected resource is enc…
Exploring the tiers of rooted phylogenetic network space using tail moves
Remie Janssen, Mark Jones, Péter L. ErdÅs +2
Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR (rooted Subtree Prune and…
Parameterizations of Test Cover with Bounded Test Sizes
Robert Crowston, Gregory Gutin, Mark Jones +2
In the {\sc Test Cover} problem we are given a hypergraph with , and we assume that is a test cover, i.e. for every pair…
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
Sander Borst, Leo van Iersel, Mark Jones +1
We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm fo…
Maximizing All-Paths Phylogenetic Diversity: Parameterized Approaches for Networks
Mark Jones, Jannik Schestag
The paper investigates the problem of maximizing a generalized phylogenetic diversity measure on directed acyclic phylogenetic networks, showing hardness results and presenting fix…
Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound
Robert Crowston, Gregory Gutin, Mark Jones
An oriented graph is a directed graph without directed 2-cycles. Poljak and TurzÃk (1986) proved that every connected oriented graph on vertices and arcs contains an a…
Challenges for the interaction region design of the Future Circular Collider FCC-ee
Manuela Boscolo, Nicola Bacchetta, Michael Benedikt +19
The FCC-ee is a proposed future high-energy, high-intensity and high-precision lepton collider. Here, we present the latest development for the FCC-ee interaction regions, which sh…
A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application
Gregory Gutin, Mark Jones, Dominik Scheder +1
Let F be a CNF formula with n variables and m clauses. F is 3-satisfiable if for any 3 clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker…
Note on Max Lin-2 above Average
Robert Crowston, Gregory Gutin, Mark Jones
In the Max Lin-2 problem we are given a system of linear equations in variables over in which Equation is assigned a positive integral weight f…
Public Goods Games in Directed Networks with Constraints on Sharing
Argyrios Deligkas, Gregory Gutin, Mark Jones +2
In a public goods game, every player chooses whether or not to buy a good that all neighboring players will have access to. We consider a setting in which the good is indivisible,…
Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
Mark Jones, Jannik Schestag
For a phylogenetic tree, the phylogenetic diversity of a set A of taxa is the total weight of edges on paths to A. Finding small sets of maximal diversity is crucial for conservati…
The BigBite Calorimeter for the Super Bigbite Spectrometer Program at Jefferson Lab
Provakar Datta, Katherine Evans, Jason Bane +24
We report features of the design, construction, installation, and performance of the BigBite Calorimeter (BBCal), a lead-glass electromagnetic calorimeter constructed as part of th…
On the Workflow Satisfiability Problem with Class-Independent Constraints
Jason Crampton, Andrei Gagarin, Gregory Gutin +2
A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirem…
When are quarnets sufficient to reconstruct semi-directed phylogenetic networks?
Katharina T. Huber, Leo van Iersel, Mark Jones +2
Phylogenetic networks are graphs that are used to represent evolutionary relationships between different taxa. They generalize phylogenetic trees since for example, unlike trees, t…
Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances
Gregory Gutin, Mark Jones
We consider vectors from . The weight of such a vector is the sum of the coordinates of . The distance ratio of a set of vectors is ${\rm dr}(L):=\max \{Ï(x,…
Polynomial-Time Algorithms for Phylogenetic Inference Problems involving duplication and reticulation
Leo van Iersel, Remie Janssen, Mark Jones +2
A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Min…
Not all phylogenetic networks are leaf-reconstructible
Péter L. ErdÅs, Leo van Iersel, Mark Jones
Unrooted phylogenetic networks are graphs used to represent evolutionary relationships. Accurately reconstructing such networks is of great relevance for evolutionary biology. It h…
Making a Network Orchard by Adding Leaves
Leo van Iersel, Mark Jones, Esther Julien +1
Phylogenetic networks are used to represent the evolutionary history of species. Recently, the new class of orchard networks was introduced, which were later shown to be interpreta…
Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems
Gregory Gutin, Mark Jones, Anders Yeo
In the {\sc Hitting Set} problem, we are given a collection of subsets of a ground set and an integer , and asked whether has a -element subset that intersec…
Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks
Yukihiro Murakami, Leo van Iersel, Remie Janssen +2
Network reconstruction lies at the heart of phylogenetic research. Two well studied classes of phylogenetic networks include tree-child networks and level- networks. In a tree-c…
Evaluating the effect of different non-informative prior specifications on the Bayesian proportional odds model in randomised controlled trials: a simulation study
Chris J. Selman, Katherine J. Lee, Michael Dymock +4
Background: Ordinal outcomes combine multiple distinct ordered patient states into a single endpoint and are commonly analysed using proportional odds (PO) models in clinical trial…
Orchard Networks are Trees with Additional Horizontal Arcs
Leo van Iersel, Remie Janssen, Mark Jones +1
Phylogenetic networks are used in biology to represent evolutionary histories. The class of orchard phylogenetic networks was recently introduced for their computational benefits,…
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan +2
We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized comp…
Level- networks from shortest and longest distances
Katharina T. Huber, Leo van Iersel, Remie Janssen +3
Recently it was shown that a certain class of phylogenetic networks, called level- networks, cannot be reconstructed from their associated distance matrices. In this paper, we s…
Combining Networks using Cherry Picking Sequences
Remie Janssen, Mark Jones, Yukihiro Murakami
Phylogenetic networks are important for the study of evolution. The number of methods to find such networks is increasing, but most such methods can only reconstruct small networks…
Parameterized Algorithms for Load Coloring Problem
Gregory Gutin, Mark Jones
One way to state the Load Coloring Problem (LCP) is as follows. Let be graph and let be a 2-coloring. An edge is calle…
Max-Cut Parameterized Above the Edwards-ErdÅs Bound
Robert Crowston, Mark Jones, Matthias Mnich
We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-ErdÅs bound is fixed-parameter tractable: we give an…
A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
Jordan Dempsey, Leo van Iersel, Mark Jones +1
We present a simple 4-approximation algorithm for computing a maximum agreement forest of multiple unrooted binary trees. This algorithm applies LP rounding to an extension of a re…
Reconstructing semi-directed level-1 networks using few quarnets
Martin Frohn, Niels Holtgrefe, Leo van Iersel +2
Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstruc…
Consistency of orthology and paralogy constraints in the presence of gene transfers
Mark Jones, Manuel Lafond, Celine Scornavacca
Orthology and paralogy relations are often inferred by methods based on gene similarity, which usually yield a graph depicting the relationships between gene pairs. Such relation g…
Cutting an alignment with Ockham's razor
Mark Jones, Philippe Gambette, Leo van Iersel +4
In this article, we investigate different parsimony-based approaches towards finding recombination breakpoints in a multiple sequence alignment. This recombination detection task i…
New Measurements of the Deuteron to Proton F2 Structure Function Ratio
Debaditya Biswas, Fernando Araiza Gonzalez, William Henry +89
Nucleon structure functions, as measured in lepton-nucleon scattering, have historically provided a critical observable in the study of partonic dynamics within the nucleon. Howeve…
A general Bayesian approach to design adaptive clinical trials with time-to-event outcomes
James M. McGree, Antony M. Overstall, Mark Jones +1
Clinical trials are an integral component of medical research. Trials require careful design to, for example, maintain the safety of participants, use resources efficiently and all…
Distinguishing level-1 phylogenetic networks on the basis of data generated by Markov processes
Elizabeth Gross, Leo van Iersel, Remie Janssen +3
Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees. These networks are able to incorporate reticulate evolutionary events such a…
A Near-Linear Kernel for Two-Parsimony Distance
Elise Deen, Leo van Iersel, Remie Janssen +3
The maximum parsimony distance and the bounded-state maximum parsimony distance measure the difference between two phylogene…
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Leo van Iersel, Mark Jones, Jannik Schestag +2
We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural…
Proximity Measures for Classes of Phylogenetic Networks
Leo van Iersel, Mark Jones, Esther Julien +2
The paper defines and analyzes proximity measures that quantify how many graph modifications are needed to convert a phylogenetic network into a member of specific network classes…
Orienting undirected phylogenetic networks
Katharina T. Huber, Leo van Iersel, Remie Janssen +4
This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undir…
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Niels Holtgrefe, Leo van Iersel, Mark Jones
To measure the tree-likeness of a directed acyclic graph (DAG), a new width parameter that considers the directions of the arcs was recently introduced: scanwidth. We present the f…
Dataset for Investigating Anomalies in Compute Clusters
Diana McSpadden, Yasir Alanazi, Bryan Hess +8
The dataset was collected for 332 compute nodes throughout May 19 - 23, 2023. May 19 - 22 characterizes normal compute cluster behavior, while May 23 includes an anomalous event. T…
PyPWA: A Software Toolkit for Parameter Optimization and Amplitude Analysis
Mark Jones, Peter Hurck, William Phelps +1
PyPWA is a toolkit designed to optimize parametric models describing data and generate simulated distributions according to a model. Its software has been written within the python…
A Unifying Characterization of Tree-based Networks and Orchard Networks using Cherry Covers
Leo van Iersel, Remie Janssen, Mark Jones +2
Phylogenetic networks are used to study evolutionary relationships between species in biology. Such networks are often categorized into classes by their topological features, which…
A Wild Sheep Chase Through an Orchard
Jordan Dempsey, Leo van Iersel, Mark Jones +2
Orchards are a biologically relevant class of phylogenetic networks as they can describe treelike evolutionary histories augmented with horizontal transfer events. Moreover, the cl…
Optimal Constructions for Chain-based Cryptographic Enforcement of Information Flow Policies
Jason Crampton, Naomi Farley, Gregory Gutin +1
The simple security property in an information flow policy can be enforced by encrypting data objects and distributing an appropriate secret to each user. A user derives a suitable…
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…
Parameterized Complexity of MaxSat Above Average
Robert Crowston, Gregory Gutin, Mark Jones +2
In MaxSat, we are given a CNF formula with variables and clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let be th…
A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees
Leo van Iersel, Remie Janssen, Mark Jones +2
We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number…
Cryptographic Enforcement of Information Flow Policies without Public Information via Tree Partitions
Jason Crampton, Naomi Farley, Gregory Gutin +2
We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes…
Linear-Vertex Kernel for the Problem of Packing -Stars into a Graph without Long Induced Paths
Florian Barbero, Gregory Gutin, Mark Jones +2
Let integers and be fixed. Let be the set of graphs with no induced path on vertices. We study the problem of packing vertex-disjoint copies…
Bounds on the sequence length sufficient to reconstruct binary level- phylogenetic networks under the CFN model
Martin Frohn, Niels Holtgrefe, Leo van Iersel +2
Phylogenetic trees and networks are graphs used to model evolutionary relationships, with trees representing strictly branching histories and networks allowing for events in which…
Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments
Robert Crowston, Gregory Gutin, Mark Jones +1
In the problem {\sc Min-DESC}, we are given a digraph and an integer , and asked if there exists a set of at most arcs in , such that if we remove the arcs of $A…
Parameterized Directed -Chinese Postman Problem and Arc-Disjoint Cycles Problem on Euler Digraphs
Gregory Gutin, Mark Jones, Bin Sheng +1
In the Directed -Chinese Postman Problem (-DCPP), we are given a connected weighted digraph and asked to find non-empty closed directed walks covering all arcs of …
A third strike against perfect phylogeny
Leo van Iersel, Mark Jones, Steven Kelk
Perfect phylogenies are fundamental in the study of evolutionary trees because they capture the situation when each evolutionary trait emerges only once in history; if such events…
Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
Mark Jones, Jannik Schestag
Phylogenetic Diversity (PD) is a measure of the overall biodiversity of a set of present-day species (taxa) within a phylogenetic tree. In Maximize Phylogenetic Diversity (MPD) one…
Chinese Postman Problem on Edge-Colored Multigraphs
Gregory Gutin, Mark Jones, Bin Sheng +2
It is well-known that the Chinese postman problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in…
Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
Leo van Iersel, Mark Jones, Jannik Schestag +2
Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabili…
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
Leo van Iersel, Mark Jones, Simone Linz +1
A directed phylogenetic network is tree-child if every non-leaf vertex has a child that is not a reticulation. As a class of directed phylogenetic networks, tree-child networks are…
A Planned Jefferson Lab Experiment on Spin-Flavor Decomposition
Xiaodong Jiang, Peter Bosted, Mark Jones +1
Experiment E04-113 at Jefferson Lab Hall C plans to measure the beam-target double-spin asymmetries in semi-inclusive deep-inelastic and $\vec d(e, e^\prim…
Characterizing semi-directed phylogenetic networks and their multi-rootable variants
Niels Holtgrefe, Katharina T. Huber, Leo van Iersel +2
In evolutionary biology, phylogenetic networks are graphs that provide a flexible framework for representing complex evolutionary histories that involve reticulate evolutionary eve…
Modelling Airway Geometry as Stock Market Data using Bayesian Changepoint Detection
Kin Quan, Ryutaro Tanno, Michael Duong +7
Numerous lung diseases, such as idiopathic pulmonary fibrosis (IPF), exhibit dilation of the airways. Accurate measurement of dilatation enables assessment of the progression of di…
Iterative Plan Construction for the Workflow Satisfiability Problem
David Cohen, Jason Crampton, Andrei Gagarin +2
The \emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defi…
Evaluating the performance of Bayesian cumulative logistic models in randomised controlled trials: a simulation study
Chris J. Selman, Katherine J. Lee, Steven Y. C. Tong +2
Background: The proportional odds (PO) model is the most common analytic method for ordinal outcomes in randomised controlled trials. While parameter estimates obtained under depar…
Performance of photosensors in a high-rate environment for gas Cherenkov detectors
Chao Peng, Junqi Xie, Sylvester Joosten +10
The solenoidal large intensity device (SoLID) at Jefferson Lab will push the boundaries of luminosity for a large-acceptance detector, which necessitates the use of a light-gas thr…
Parameterized Complexity of the -Arc Chinese Postman Problem
Gregory Gutin, Mark Jones, Bin Sheng
In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph ( may have both edges and arcs), our aim is to find a minimum weight closed walk traversing e…
Constructing a Consensus Phylogeny from a Leaf-Removal Distance
Cedric Chauve, Mark Jones, Manuel Lafond +2
Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing {possi…
Structural Parameterizations of the Mixed Chinese Postman Problem
Gregory Gutin, Mark Jones, Magnus Wahlstrom
In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph ( may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each ed…
Embedding phylogenetic trees in networks of low treewidth
Leo van Iersel, Mark Jones, Mathias Weller
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arise…
Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
Mark Jones, Steven Kelk, Leen Stougie
Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results a…
Polynomial Kernels for λ-extendible Properties Parameterized Above the Poljak-TurzÃk Bound
Robert Crowston, Mark Jones, Gabriele Muciaccia +3
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that f…
Acyclicity in Edge-Colored Graphs
Gregory Gutin, Mark Jones, Bin Sheng +2
A walk in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in is of different color. We introduce and study five types of PC acyclicit…
Tree Containment Parameterized by Scanwidth
Leo van Iersel, Mark Jones, Mathias Weller
TREE CONTAINMENT is a central decision problem in mathematical phylogenetics, asking whether a given rooted phylogenetic tree is embeddable in ("displayed by") a given rooted phylo…