Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. SCCS can also be solved by a greedy algorithm. Here, we propose a linear time algorithm for solving SCCS based on a Eulerian graph that captures all greedy solutions in linear space. Because the graph is Eulerian, this algorithm can also find a greedy solution of SCCS with the least number of cyclic strings. This has implications for solving certain instances of the Shortest linear or cyclic Superstring problems. 相似文献
Let V be a finite set with |V|=n. A family F⊆2V is called laminar if for all two sets X,Y∈F, X∩Y≠∅ implies X⊆Y or X⊇Y. Given a laminar family F, a demand function , and a monotone concave cost function , we consider the problem of finding a minimum-cost such that x(X)?d(X) for all X∈F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n2q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any . We also prove that if F is given by an oracle, then it takes Ω(n2q) time to solve the problem, which implies that our O(n2q) time algorithm is optimal in this case. Furthermore, we propose an algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires Ω(2n/2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form. 相似文献
Certain identities of Ramanujan may be succinctly expressed in terms of the rational function
on the modular curve X0(N), where
and fχ is a certain modular unit on the Nebentypus cover Xχ(N) introduced by Ogg and Ligozat for prime
and wN is the Fricke involution. These correspond to levels N=5,13, where the genus gN of X0(N) is zero. In this paper we study slightly more general kind of relations for each
such that X0(N) has genus gN=1,2, and also for each
such that the Atkin–Lehner quotient X0+(N) has genus gN+=1,2. Finally we study the normal closure of the field of definition of the zeros of the latter.
相似文献
A cover of the non-incident point-hyperplane graph of projective dimension 3 for fields of characteristic 2 is constructed.
For fields
of even order larger than 2, this leads to an elementary construction of the non-split extension of SL4(
)by
6. 相似文献
The convexity number of a set is the least size of a family of convex sets with . is countably convex if its convexity number is countable. Otherwise is uncountably convex.
Uncountably convex closed sets in have been studied recently by Geschke, Kubis, Kojman and Schipperus. Their line of research is continued in the present article. We show that for all , it is consistent that there is an uncountably convex closed set whose convexity number is strictly smaller than all convexity numbers of uncountably convex subsets of .
Moreover, we construct a closed set whose convexity number is and that has no uncountable -clique for any 1$">. Here is a -clique if the convex hull of no -element subset of is included in . Our example shows that the main result of the above-named authors, a closed set either has a perfect -clique or the convexity number of is in some forcing extension of the universe, cannot be extended to higher dimensions.
This paper considers variations of the minimum connected vertex cover problem to be found in the study of wireless network design. A simple, theoretic formulation is followed by a discussion of practical constraints. Two algorithms are given and results compared. 相似文献