FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees [0.03%]
全基因综合分析：一致基因树的数据集的同源协调
Mathieu Gascon,Mattéo Delabre,Nadia El-Mabrouk
Mathieu Gascon
We present FullSynesth, a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or syntenies, inside a species tree. The considered evolutionary model involves segmental events (i.e. acting on multipl...
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths [0.03%]
顶点不相交最短路径的紧近似和核化界
Matthias Bentert,Fedor V Fomin,Petr A Golovach
Matthias Bentert
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) n-vertex graph G along with k terminal pairs ( s 1 , t 1 ) , ( s 2 , t 2 ) , …...
Irving van Heuven van Staereling,Bart de Keijzer,Guido Schäfer
Irving van Heuven van Staereling
We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph [Formula: see text], where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set ...
Narad Rampersad,Jeffrey Shallit
Narad Rampersad
We show how to obtain, via a unified framework provided by logic and automata theory, many classical results of Brillhart and Morton on Rudin-Shapiro sums. The techniques also facilitate easy proofs for new results. ...
Alexey Milovanov
Alexey Milovanov
We combine Solomonoff's approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best "explanation" for the observed data (in the sense of algorithmic statistics) for predictio...
Michaël Cadilhac,Filip Mazowiecki,Charles Paperman et al.
Michaël Cadilhac et al.
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (...
Faith Ellen,Rati Gelashvili,Philipp Woelfel et al.
Faith Ellen et al.
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated ...
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection [0.03%]
带投影的简单良好设计模式树的可计算性特征研究
Stefan Mengel,Sebastian Skritek
Stefan Mengel
We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtainin...
Eleni C Akrida,Leszek Gąsieniec,George B Mertzios et al.
Eleni C Akrida et al.
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from ...
Simone Bova,Friedrich Slivovsky
Simone Bova
We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we prove that variable convex formulas (that is, formulas with incidence graphs that are convex with respect to the set...