The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. ...

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the ...

The maximum parsimony distance d MP ( T 1 , T 2 ) and the bounded-state maximum parsimony distance d MP t ( T 1 , T 2 ) measure the difference between two phylogenetic trees T 1 , T 2 in terms of the maximum difference between their parsimony ...

A garden is populated by n bamboos, each with its own daily growth rate. The Bamboo Garden Trimming Problem (BGT) is to design for a robotic gardener a perpetual schedule of cutting bamboos to keep the elevation of the garden as low as possible. ...

In the study of rooted phylogenetic networks, analyzing the set of rooted phylogenetic trees that are embedded in such a network is a recurring task. Algorithmically, this analysis requires a search of the exponential-sized multiset S ...

The Moran process, as studied by Lieberman, Hauert and Nowak (2005) [1], is a birth-death process that models the spread of mutations in two-type populations (residents-mutants) whose structure is defined by a digraph. The process' ...

A robot game, also known as a Z-VAS game, is a two-player vector addition game played on the integer lattice Z n, where one of the players, Adam, aims to avoid the origin while the other player, Eve, aims to reach the origin. The ...

Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We introduce a new ...

Many hardness results in computational social choice use the fact that every digraph may be induced as the pairwise majority relation of some preference profile. The standard construction requires a number of voters that is almost ...

Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between ...

DNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent ...

This article proposes a new algorithm that improves the complexity bound for solving parity games. Our approach combines McNaughton's iterated fixed point algorithm with a preprocessing step, which is called prior to every recursive call. The ...

The notion of time-free solution to decision problem by P systems with proteins on membranes, in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, is defined.A time-free uniform solution to the ...

We presented formal models for disease diagnosis schemes.We defined formal representations for disease diagnosis rules.We defined analytics methods for implementing the diagnosis schemes.We presented a result of applying the diagnosis schemes to a ...

P systems are abstract distributed computing models inspired by the information flows in living cells and their networks, with applications, e.g., in systems biology and optimization. A tissue P system is a variant based on the interchange of objects ...

The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour ...

In the last decade, the interest in microarray technology has exponentially increased due to its ability to monitor the expression of thousands of genes simultaneously. The reconstruction of gene association networks from gene expression profiles is a ...

With the advent of new sequencing technologies able to produce an enormous quantity of short genomic sequences, new tools able to search for them inside a genomic reference sequence have emerged. Because of chemical reading errors or of the variability ...

We show how a layered Cloud service model of software (SaaS), platform (PaaS), and infrastructure (IaaS) leverages multiple independent Clouds by creating a federation among the providers. The layered architecture leads naturally to a design in which ...