共查询到20条相似文献,搜索用时 227 毫秒
1.
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. 相似文献
2.
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1. 相似文献
3.
Suppose T is an incidence, basis circuit or basis cut set matrix of a connected graph and T(k) is the k compound of T. It is proven that any second order minor of T(k) is equal +1, −1, or 0. For the case of an incidence matrix this result is applied to tree counting and some structural properties of T(k) are given. 相似文献
4.
The k nearest neighbor rule ( k-NNR) is a well-known nonparametric decision rule in pattern classification. Fuzzy set theory has been widely used to represent the uncertainty of class membership. Several researchers extended conventional k-NNR to fuzzy k-NNR, such as Bezdek et al. [ Fuzzy Sets and Systems 18 (1986) 237–256], Keller et al. [ IEEE Trans. Syst. Man, and Cybern. 15(4) (1985) 580–585], Béreau and Dubuisson [ Fuzzy Sets and Systems 44 (1991) 17–32]. In this paper, we describe a fuzzy generalized k-NN algorithm. This algorithm is a unified approach to a variety of fuzzy k-NNR's. Then we create the strong consistency of posterior risk of the fuzzy generalized NNR. 相似文献
5.
For a positive integer k2, the k-Fibonacci sequence { gn(k)} is defined as: g1(k)== gk−2(k)=0, gk−1(k)= gk(k)=1 and for n> k2, gn(k)= gn−1(k)+ gn−2(k)++ gn−k(k). Moreover, the k-Lucas sequence { ln(k)} is defined as ln(k)= gn−1(k)+ gn+k−1(k) for n1. In this paper, we consider the relationship between gn(k) and ln(k) and 1-factors of a bipartite graph. 相似文献
6.
In the present article we concentrate our study on the growth problem for the weighing matrix W(12,11) and show that the unique W(12,11) has three pivot structures. An improved algorithm for extending a k?×? k (0,+,-) matrix to a W(n,n-1), if possible, has been developed to simplify the proof. For the implementation of the algorithm special emphasis is given to the notions of data structures and parallel processing. 相似文献
7.
We give safety neighbourhoods for the necessary conditions in the change of the Jordan canonical form of a matrix under small perturbations. We also obtain the minimum distance from an n × n complex matrix which has less than k nonconstant invariant factors (2≤ k≤ n) to the set of matrices which have more or equal to k. When k= 2, we get in particular the distance from a nonderogatory matrix to the set of derogatory matrices. 相似文献
8.
图 G的正常[ k]-边染色 σ是指颜色集合为[ k]={1,2,…, k}的 G的一个正常边染色.用 wσ( x)表示顶点 x关联边的颜色之和,即 wσ( x)=∑ e∋x σ( e),并称 wσ( x)关于 σ的权.图 G的 k-邻和可区别边染色是指相邻顶点具有不同权的正常[ k]-边染色,最小的 k值称为 G的邻和可区别边色数,记为 χ' ∑( G).现得到了路 Pn与简单连通图 H的字典积 Pn[ H]的邻和可区别边色数的精确值,其中 H分别为正则第一类图、路、完全图的补图. 相似文献
9.
Let A be an nk × nk positive semi-definite symmetric matrix partitioned into blocks Aij each of which is an n × n matrix. In [2] Mine states a conjecture of Marcus that per( A) ≥ per( G) where G is the k × k matrix [per( Aij)]. In this paper we prove a weaker inequality namely that per( A) ≥ ( k!) -1per( G). 相似文献
10.
Let S1 and S2 be two ( k-1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E( H) such that S1 ∩ e ≠∅ and S2 ∩ e ≠∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2 k2- k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent ( k-1)-sets equal to 2 n-4( k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+( k-2) k. If the degree sum of any two middle independent ( k-1)-subsets is larger than 2( d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent ( k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. 相似文献
11.
We are concerned with the behavior of the minimum (maximum) eigenvalue λ0(n) ( λn(n)) of an ( n + 1) × ( n + 1) Hermitian Toeplitz matrix Tn( ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ0(n) — min ƒ = O(1/ n2k) in the case where ƒ C2k, at least locally, and ƒ — inf ƒ has a zero of order 2 k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ0(n) to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L1 functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ. 相似文献
12.
For a given real or complex polynomial p of degree n we modify the Euclidean algorithm to find a general tridiagonal matrix representation T of the monic version of p and then use the tridiagonal DQR eigenvalue algorithm on T in order to find all roots of p with their multiplicities in O( n2) operations and 0( n) storage. We include details of the implementation and comparisons with several, standard and recent, essentially 0( n3) polynomial root finders. 相似文献
13.
We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O( n2) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(log n) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log 2n+ k) time. 相似文献
14.
If a square matrix has a nonnegarive power it is called a property- n matrix. In a recent paper [12] Werner derived some interesting necessary and sufficient conditions for a property n property- n matrix to be Drazin-montone. In particular, it was shown that a property - n matrix with ind( A) = k is Drazin-monotone if and only if A2k+1 is weak- r-monotone. Our principal aim here is to show how this result can he strengthened considerably. To tackle this problem we also present several further results on the structure of Drazin-monotone (property- n) matrices. 相似文献
15.
We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ s( n)log 3n), where s is the maximum number of intersections between the boundaries of the ( xy-projections) of any pair of objects, and λ s( n) is the maximum length of ( n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ s( n)log 2n). The query time in the first problem is O(log 4n), the query time in the second and third problems is O(log 3n + klog 2n), and the query time in the fourth problem is O(log 3n). We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K1, K2 and K1 lies vertically above K2, then K1 precedes K2.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm. 相似文献
16.
We consider embeddings of the complete t-ary trees of depth k (denotation Tk,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim( Tk,t), is known if max{ k, t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim( Tk,3)2 k+1 up to lim k→∞dim( Tk,3)/ k5/3 and show lim t→∞dim( T3,t)/ t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim( Tk,t) for arbitrary k and t. 相似文献
17.
We obtain an approximation for the logarithmic averages of I{ k1/2a( k) S( k) k1/2b( k)}, where a( k) → 0, b( k) → 0 ( k → ∞) and S( k) is partial sum of independent, identically distributed random variables. 相似文献
18.
For each positive integer k we consider the smallest positive integer f( k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ( G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, …, xp-1 of the same class with dist( xi, xi+1) f( k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f( k) from the remainder of the class. We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1. 相似文献
19.
The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤ k≤8 and n> k + 5) with the minimal least eigenvalue. 相似文献
20.
Let G be a k-regular vertex transitive graph with connectivity κ( G)= k and let mk( G) be the number of vertex cuts with k vertices. Define m(n,k)=min {mk(G): GTn,k}, where Tn,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ( G)= k. In this paper, we determine the exact values of m( n, k). 相似文献
|