A lot of research has been done in the field of graph coloring, yet there are no publicly released libraries available. This paper introduces such a library. This library is designed to meet several important criteria...
详细信息
The paper deals with the problem of finding a tandem scattered subsequence of maximum length (LTS) for a given character sequence. A sequence is referred to as tandem if it can be split into two identical sequences. A...
详细信息
The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search stra...
详细信息
We consider the Chromatic Sum Problem on bipartite graphs which appears to be much harder than the classical Chromatic Number Problem. We prove that the Chromatic Sum Problem is NP-complete on planar bipartite graphs ...
详细信息
In the paper, we describe a method for comparing arbitrary, not necessary fully resolved, un rooted phylogenetic trees. The proposed method is based on finding a minimum weight matching in bipartite graphs and can be ...
详细信息
ISBN:
(纸本)9788360779026
In the paper, we describe a method for comparing arbitrary, not necessary fully resolved, un rooted phylogenetic trees. The proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of the presented distance in a common biological problem of finding a single phylogenetic tree (consensus tree) that reliably represents a set of various phylogenetic trees. Finding a consensus tree (or a small set of such trees) is an important phase in the phylogenetic research, especially if a method that is chosen for the construction process returns a set of trees (for example the very popular Bayesian approach).
One of the important problems in evolutionary biology is inferring phylogenetic trees for sets of related species, We introduce a new model for inferring phylogenies which is a generalization of the widely studied per...
详细信息
It is proven that the connected pathwidth of any graph G is at most 2 · pw(G) + 1, where pw(G) is the pathwidth of G. The method is constructive, i.e., it yields an efficient algorithm that for a given path decom...
详细信息
Let S(v) denote a nonempty set of integers assigned, to vertex v of graph G = (V, E). Let us call S a list assignment for G. We look for a legal graph coloring f such that for every vertex v ∈ V we have f(v) ∈ S(v)....
详细信息
A phylogenetic tree represents historical evolutionary relationship between different species or organisms. There are various methods for reconstructing phylogenetic trees. Applying those techniques usually results in...
详细信息
Quantum mechanics has greatly impacted our understanding of microscopic nature. One of the key concepts of this theory is generalized measurements, which have proven useful in various quantum information processing ta...
详细信息
Quantum mechanics has greatly impacted our understanding of microscopic nature. One of the key concepts of this theory is generalized measurements, which have proven useful in various quantum information processing tasks. However, despite their significance, they have not yet been shown empirically to provide an advantage in quantum randomness certification and expansion protocols. This investigation explores scenarios where generalized measurements can yield more than 1 bit of certified randomness with a single-qubit system measurement on untrusted devices and against a quantum adversary. We compare the robustness of several protocols to exhibit the advantage of exploiting generalized measurements. In our analysis of experimental data, we were able to obtain 1.21 bits of min-entropy from a measurement taken on one qubit of an entangled state. We also obtained 1.07 bits of min-entropy from an experiment with quantum state preparation and generalized measurement on a single qubit. We also provide finite data analysis for a protocol using generalized measurements and the Entropy Accumulation Theorem. Our exploration demonstrates the potential of generalized measurements to improve the certification of quantum sources of randomness and enhance the security of quantum cryptographic protocols and other areas of quantum information.
暂无评论