首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 390 毫秒
1.
An orthonormal frame (f1,f2,f3)(f1,f2,f3) is rotation-minimizing   with respect to fifi if its angular velocity ω   satisfies ωfi≡0ωfi0 — or, equivalently, the derivatives of fjfj and fkfk are both parallel to fifi. The Frenet frame (t,p,b)(t,p,b) along a space curve is rotation-minimizing with respect to the principal normal p, and in recent years adapted frames that are rotation-minimizing with respect to the tangent t have attracted much interest. This study is concerned with rotation-minimizing osculating   frames (f,g,b)(f,g,b) incorporating the binormal b, and osculating-plane vectors f, g that have no rotation about b. These frame vectors may be defined through a rotation of t, p by an angle equal to minus the integral of curvature with respect to arc length. In aeronautical terms, the rotation-minimizing osculating frame (RMOF) specifies yaw-free rigid-body motion along a curved path. For polynomial space curves possessing rational Frenet frames, the existence of rational RMOFs is investigated, and it is found that they must be of degree 7 at least. The RMOF is also employed to construct a novel type of ruled surface, with the property that its tangent planes coincide with the osculating planes of a given space curve, and its rulings exhibit the least possible rate of rotation consistent with this constraint.  相似文献   

2.
Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial nO(k)nO(k) time brute force algorithm for finding a kk-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅nO(1)f(k)nO(1)) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ??, then we can determine in randomized time f(k,?)⋅nO(1)f(k,?)nO(1) whether there is an independent set that is the union of kk blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a kk-element set in the intersection of ?? matroids, or finding kk terminals in a network such that each of them can be connected simultaneously to the source by ?? disjoint paths.  相似文献   

3.
The software package Qcompiler (Chen and Wang 2013) provides a general quantum compilation framework, which maps any given unitary operation into a quantum circuit consisting of a sequential set of elementary quantum gates. In this paper, we present an extended software OptQC  , which finds permutation matrices PP and QQ for a given unitary matrix UU such that the number of gates in the quantum circuit of U=QTPTUPQU=QTPTUPQ is significantly reduced, where UU is equivalent to UU up to a permutation and the quantum circuit implementation of each matrix component is considered separately. We extend further this software package to make use of high-performance computers with a multiprocessor architecture using MPI. We demonstrate its effectiveness in reducing the total number of quantum gates required for various unitary operators.  相似文献   

4.
Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon–Schützenberger Theorem, which says that every solution of the equation ambn=ckambn=ck over Σ*Σ* is trivial.  相似文献   

5.
We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂RkSRk defined by a weak sign condition involving ss polynomials in Z[X1,…,Xk]Z[X1,,Xk] having degrees at most dd, and whose coefficients have bitsizes at most ττ. Our bound is an explicit function of s,d,ks,d,k and ττ, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of SS (including the unbounded components). While asymptotic bounds of the form 2τdO(k)2τdO(k) on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,ks,d,k and ττ. The bounds proved in this paper are of this nature.  相似文献   

6.
7.
Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible.  相似文献   

8.
9.
10.
A collection of T1,T2,…,TkT1,T2,,Tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree TT such that each tree TiTi can be obtained from TT by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(nk)Ω(nk) time, nn being the number of leaves. Here, we present an O(nf(k))O(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number kk of trees.  相似文献   

11.
Given a graph GG, an integer kk, and a demand set D={(s1,t1),…,(sl,tl)}D={(s1,t1),,(sl,tl)}, the kk-Steiner Forest problem finds a forest in graph GG to connect at least kk demands in DD such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n2/3logl)O(n2/3logl). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n2/3logk)O(n2/3logk) via greedy approach, improving the previously best known ratio in the literature.  相似文献   

12.
In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4n)O(4n) constraints whose coefficients belong to {−1,0,1}{1,0,1}. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(kmax2n)O(kmax2n), where kmax is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.  相似文献   

13.
New computational topology techniques are presented for surface reconstruction of 2-manifolds with boundary, while rigorous proofs have previously been limited to surfaces without boundary. This is done by an intermediate construction of the envelope   (as defined herein) of the original surface. For any compact C2C2-manifold MM embedded in R3R3, it is shown that its envelope is C1,1C1,1. Then it is shown that there exists a piecewise linear (PL) subset of the reconstruction of the envelope that is ambient isotopic to MM, whenever MM is orientable. The emphasis of this paper is upon the formal mathematical proofs needed for these extensions. (Practical application examples have already been published in a companion paper.) Possible extensions to non-orientable manifolds are also discussed. The mathematical exposition relies heavily on known techniques from differential geometry and topology, but the specific new proofs are intended to be sufficiently specialized to prompt further algorithmic discoveries.  相似文献   

14.
We study the state complexity of certain simple languages. If AA is an alphabet of kk letters, then a kk-language   is a nonempty set of words of length kk, that is, a uniform language of length kk. We show that the minimal state complexity of a kk-language is k+2k+2, and the maximal, (kk−1−1)/(k−1)+2k+1(kk11)/(k1)+2k+1. We prove constructively that, for every ii between the minimal and maximal bounds, there is a language of state complexity ii. We introduce a class of automata accepting sets of words that are permutations of AA; these languages define a complete hierarchy of complexities between k2−k+3k2k+3 and 2k+12k+1. The languages of another class of automata, based on kk-ary trees, define a complete hierarchy of complexities between 2k+12k+1 and (kk−1−1)/(k−1)+2k+1(kk11)/(k1)+2k+1. This provides new examples of uniform languages of maximal complexity.  相似文献   

15.
16.
17.
Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω   over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T?T? of minimum cost ω(T?)ω(T?) rooted at r and spanning X.  相似文献   

18.
19.
20.
Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language ?PΠPΣ?P?PΠPΣ?P (swap automaton, for short), where ΠPΠP is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ?PΣ?P. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ2⌈k/w⌉)O(σ2k/w) space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)O(nk/w), where ⌈m/σ⌉?k?mm/σ?k?m is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.  相似文献   

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

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