首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f1(x),…,fm(x),y1,…,yn), where pQ[x,t1,…,tm,y1,…,yn] and f1(x),…,fm(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f1(x),…,fm(x)]. In particular, the algorithm applies when f1(x),…,fm(x) are real exp-log functions or tame elementary functions.  相似文献   

2.
Let F1,…,FsR[X1,…,Xn] be polynomials of degree at most d, and suppose that F1,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F1,…,Fs.For any point xRn, we consider the task of determining the signs of the values F1(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F1,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F1,…,Fs belong to Z[X1,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F1,…,Fs.  相似文献   

3.
Given q+1 strings (a text t of length n and q patterns m1,…,mq) and a natural number w, the multiple serial episode matching problem consists in finding the number of size w windows of text t which contain patterns m1,…,mq as subsequences, i.e., for each mi, if mi=p1,…,pk, the letters p1,…,pk occur in the window, in the same order as in mi, but not necessarily consecutively (they may be interleaved with other letters). Our main contribution here is an algorithm solving this problem on-line in time O(nq) with an MP-RAM model (which is a RAM model equipped with extra operations).  相似文献   

4.
Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv,wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P=〈v1,v2,…,vk〉 is defined as . The weight of P, denoted by w(P), is . Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O(wmaxnL)-time algorithm to find a maximum-density path P in T such that wmin?w(P)?wmax and the length of P is at least L.  相似文献   

5.
Let P1,…,Pk be a collection of disjoint point sets in R2 in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T1,…,Tk intersect at most , where n is the number of points in P1∪?∪Pk. If the intersection of the convex hulls of P1,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |PQ|=n (the weight of an edge is its length).  相似文献   

6.
We construct an explicit minimal strong Gröbner basis of the ideal of vanishing polynomials in the polynomial ring over Z/m for m≥2. The proof is done in a purely combinatorial way. It is a remarkable fact that the constructed Gröbner basis is independent of the monomial order and that the set of leading terms of the constructed Gröbner basis is unique, up to multiplication by units. We also present a fast algorithm to compute reduced normal forms, and furthermore, we give a recursive algorithm for building a Gröbner basis in Z/m[x1,x2,…,xn] along the prime factorization of m. The obtained results are not only of mathematical interest but have immediate applications in formal verification of data paths for microelectronic systems-on-chip.  相似文献   

7.
In an undirected graph, paths P1,P2,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s1,t1},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound.  相似文献   

8.
A multi-secret sharing scheme is a protocol to share m arbitrarily related secrets s1, … , sm among a set of n participants. In this paper, we propose an ideal linear multi-secret sharing scheme, based on monotone span programs, where each subset of the set of participants may have the associated secret. Our scheme can be used to meet the security requirement in practical applications, such as secure group communication and privacy preserving data mining etc. We also prove that our proposed scheme satisfies the definition of a perfect multi-secret sharing scheme.  相似文献   

9.
We present a simple and faster solution to the problem of matching a set of patterns with variable length don't cares. Given an alphabet Σ, a pattern p is a word p1@p2?@pm, where pi is a string over Σ called a keyword and @∉Σ is a symbol called a variable length don't care (VLDC) symbol. Pattern p matches a text t if t=u0p1u1um−1pmum for some u0,…,umΣ. The problem addressed in this paper is: given a set of patterns P and a text t, determine whether one of the patterns of P matches t.Kucherov and Rusinowitch (1997) [9] presented an algorithm that solves the problem in time O((|t|+|P|)log|P|), where |P| is the total length of keywords in every pattern of P. We give a new algorithm based on Aho-Corasick automaton. It uses the solutions of Dynamic Marked Ancestor Problem of Chan et al. (2007) [5]. The algorithm takes O((|t|+‖P‖)logκ/loglogκ) time, where ‖P‖ is the total number of keywords in every pattern of P, and κ is the number of distinct keywords in P. The algorithm is faster and simpler than the previous approach.  相似文献   

10.
String matching is the problem of finding all the occurrences of a pattern P in a text T, where P and T are strings over a finite alphabet Σ. A variable length don′t care is a special character, not belonging to Σ, which can match any string in Σ*. The string-matching problem with variable length don′t cares is an extension of the classical string-matching problem in which the pattern P may contain an arbitrary number of don′t cares. An efficient parallel algorithm is given for solving the string-matching problem with variable length don′t cares. The EREW PRAM model of parallel computer with scan operations is used to obtain an O(log n) running time using O(mn/log n) processors, where m and n are, respectively, the lengths of P and T. The proposed parallel algorithm has an Ω(1/log n) processor utilization, since the fastest serial algorithm known so far has an O(mn/log n) running time.  相似文献   

11.
The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s1,t1},…,{sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1?i?m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f(k)⋅nO(1), we can either find a solution of size 2k or correctly conclude that there is no solution of size k.The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.  相似文献   

12.
13.
14.
We consider the alignment problem where sequences may have masked regions. The bases in masked regions are either unspecified or unknown, and they will be denoted by N. We present an efficient algorithm that finds an optimal local alignment by skipping such masked regions of sequences. Our algorithm works for both the affine gap penalty model and the linear gap penalty model. The time complexity of our algorithm is O((nT)(mS)+vm+wn) time, where n and m are the lengths of given sequences A and B, T and S are the numbers of base N in A and B, and v and w are the numbers of masked regions in A and B, respectively.  相似文献   

15.
16.
We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm+n2logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance μ(v,w) between each pair v,w of vertices even in the presence of negative cycles, where μ(v,w) is defined as the infimum of the costs of all directed paths from v to w.  相似文献   

17.
We present explicit solutions of a class of recurrences related to the Quickselect algorithm. Thus we are immediately able to solve recurrences arising at the partial sorting problem, which are contained in this class. Furthermore we show how the partial sorting problem is connected to the Multiple Quickselect algorithm and present a method for the calculation of solutions for a class of recurrences related to the Multiple Quickselect algorithm. Further an analysis of an algorithm for sorting a subarray A[rr+p−1], given the array A[1…n], is provided.  相似文献   

18.
A distributed XML document is an XML document that spans several machines. We assume that a distribution design of the document tree is given, consisting of an XML kernel-documentT[f1,…,fn] where some leaves are “docking points” for external resources providing XML subtrees (f1,…,fn, standing, e.g., for Web services or peers at remote locations). The top-down design problem consists in, given a type (a schema document that may vary from a DTD to a tree automaton) for the distributed document, “propagating” locally this type into a collection of types, that we call typing, while preserving desirable properties. We also consider the bottom-up design which consists in, given a type for each external resource, exhibiting a global type that is enforced by the local types, again with natural desirable properties. In the article, we lay out the fundamentals of a theory of distributed XML design, analyze problems concerning typing issues in this setting, and study their complexity.  相似文献   

19.
We consider the problem of preemptively scheduling n imprecise computation tasks on m?1 uniform processors, with each task Ti having two weights wi and . Three objectives are considered: (1) minimizing the maximum w-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w-weighted error is minimized; (3) minimizing the maximum w-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn4), O(mn4) and O(kmn4), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn3), O(cmn3+mn4) and O(kcmn3), respectively, where c is a parameter-dependent number.  相似文献   

20.
Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex vV?T, there exist u,wT (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号