首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 125 毫秒
1.
Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G.  相似文献   

2.
In this paper, the weighted tailored 2-partition problem and the weighted 2-center problem under l-distance are considered. An O(2d−1·d·n) algorithm to solve the weighted tailored 2-partition problem and an O(d2·n + d2·log*d) time algorithm to solve the weighted 2-center problem in the d-dimensional case are presented.  相似文献   

3.
We present an extension of the Combination Lemma of Guibas et al. (1983) that expresses the complexity of one or several faces in the overlay of many arrangements (as opposed to just two arrangements in (Guibas et al. 1989)), as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applications of the new Combination Lemma are presented. We first show that the complexity of a single face in an arrangement of k simple polygons with a total of n sides is Θ(n(k)), where (·) is the inverse of Ackermann's function. We also give a new and simpler proof of the bound on the total number of edges of m faces in an arrangement of n Jordan arcs, each pair of which intersect in at most s points, where λs(n) is the maximum length of a Davenport–Schinzel sequence of order s with n symbols. We extend this result, showing that the total number of edges of m faces in a sparse arrangement of n Jordan arcs is , where w is the total complexity of the arrangement. Several other related results are also obtained.  相似文献   

4.
A probabilistic version of the method of feasible directions (MFD) for solving nonlinear programming (NLP) problems of the type min{f(x): fj(x)0,j=1,2,…,m} is presented. Randomization is applied to modify the algorithm and a global convergence Theorem is used in the analysis of convergence. Some numerical experiments on problems with known solutions serve to compare this method with the traditional deterministic versions.  相似文献   

5.
It is shown that any m×n±1 matrix may be embedded in a Hadamard matrix of order kl, where k and l are the least orders greater than or equal to m and nrespectively in which Hadamard matrices exist.  相似文献   

6.
In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an Sλ(t,k,v) such that
then there exists an Sλ(vt+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns Sλ(t,k,v). Moreover, if Bi and Bj are any two blocks belonging to two distinct such subdesigns, then d|BiBj|<kh. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an Sλ(t,k,v) such that
where m=min{s,vk} and n=min{i,t}, then there exists an
having pairwise disjoint subdesigns Sλ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.  相似文献   

7.
Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog3n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n2) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n2) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.  相似文献   

8.
Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n2(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.  相似文献   

9.
Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m2n2), where m is the number of vertices of P and n is the number of points in X.  相似文献   

10.
The thermal equilibrium state of two oppositely charged gases confined to a bounded domain , m = 1,2 or m = 3, is entirely described by the gases' particle densities p, n minimizing the total energy (p, n). it is shown that for given P, N > 0 the energy functional admits a unique minimizer in {(p, n) ε L2(Ω) x L 2(Ω) : p, n ≥ 0, Ωp = P, Ωn = N} and that p, n ε C(Ω) ∩ L(Ω).

The analysis is applied to the hydrodynamic semiconductor device equations. These equations in general possess more than one thermal equilibrium solution, but only the unique solution of the corresponding variational problem minimizes the total energy. It is equivalent to prescribe boundary data for electrostatic potential and particle densities satisfying the usual compatibility relations and to prescribe Ve and P, N for the variational problem.  相似文献   


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

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

京公网安备 11010802026262号