Construction and algebraic characterizations of a planar four-index transportation problem equivalent to a circularization network flow problem

In this study, a circularization network flow problem with m?+?n?+?2 nodes and (m?+?1)(n?+?1) arcs is described as a planar four-index transportation problem of order 1?×?m?×?n?×?1. Construction and several algebraic characterizations of the planar four-index transportation problem of order 1?×?m?×?n?×?1 are investigated using the generalized inverse and singular value decomposition of its coefficient matrix. The results are compared with some results we obtained on the transportation problem with m sources and n destinations. It is shown that these problems can be solved in terms of eigenvectors of the matrices J _m and J _n , where J _m is a m?×?m matrix whose entries are 1.     

Further oscillation criteria for delay partial difference equations

This paper is concerned with the partial difference equation A_m+1,n+A_m,n+1−A_m,n+p_m,nA_m−k,n−l=0,m,n=0,1,2,…,, where k and l are two positive integers, {p_m,n} is a real double sequence. Some new oscillation criteria for this equation are obtained.     

Improving the panconnectedness property of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a promising alternative to the hypercube because of its great properties. Not only is LTQ_n n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQ_n for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m?1?r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQ_n is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu.     

Four rendezvous problems for n non-identical simple-integral plants

Four rendezvous problems for n non-identical simple-integral plants (K ₁/s, K₂/s,[tdot],K_n/s), with a common input x(t) = A_mi^m u(t), m = 0,1,2,[tdot], and initial output conditions of (ξ₁,ξ₂,[tdot], ξ_n), are studied in this paper. These rendezvous problems, generally speaking, are concerned with transferring the n plants outputs to meet one another in a finite time (at a. fixed target or on a non-stationary one).     

Star graph automorphisms and disjoint Hamilton cycles

The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies. We define automorphisms for star graphs St _n of degree n?1, for every positive odd integer n, which yield permutations of labels for the edges of St _n taken from the set of integers between 1 and ? n/2 ?. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known Hamilton cycle in St _n . Our method produces a better than two-fold improvement from ? ? (n)/10 ? to ? 2? (n)/9 ?, where ? is the Euler function, for the known number of edge-disjoint Hamilton cycles in St _n for all odd integers n. For prime n, the improvement is from ? n/8 ? to ? n/5 ?, and we can extend this result to the case when n is the power of a prime greater than 7.     

Right,left characteristic sequences and column,row minimal indices of a singular pencil

For a general singular pencil sF — G?? ^m×n [s] the right, left characteristic sequences _r(F, G), _l(F, G) are defined and they are shown to be of the piecewise arithmetic progression type. The sets of column, row minimal indices ?_c(F, G), ?_r(F, G) are defined by a singular points analysis of _r(F, G), ?_l(F, G) respectively. Thus, ?_c(F, G), ?_r(F, G) emerge as numerical invariants of the ordered pair (F, G) and they may be computed by rank tests on Toeplitz matrices defined on (F, G).     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].     

Incomplete crossed hypercubes

In this paper, a new interconnection network called the incomplete crossed hypercube is proposed for connecting processors of parallel computing systems. The incomplete crossed hypercube architecture denoted by CI _n−m ⁿ is made by combining two complete crossed hypercubes CQ _n and CQ _n−m for 1≤m≤n. Several topological properties of CI _n−m ⁿ are analyzed. In particular, accurate mean internode distance formulas of both CQ _n and CI _n−m ⁿ are given. Compared with the incomplete enhanced hypercube EI _n−m ⁿ , CI _n−m ⁿ has shorter mean internode distance for large n. An optimal routing algorithm for CI _n−m ⁿ is also described which guarantees the generation of a shortest path from a node to another in CI _n−m ⁿ .     

The rupture degree of trees

For the complete graph K _n , its rupture degree is defined as 1?n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G ? X)?|X|?m(G ? X):X ? V(G), ω(G ? X) > 1 }, where ω(G ? X) is the number of components of G ? X and m(G ? X) is the order of a largest component of G ? X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.     

A class of boolean functions with linear combinational complexity

In this paper we investigate the combinational complexity of Boolean functions satisfying a certain property, ⁿ_k,m. A function of n variables has the ⁿ_k,m property if there are at least m functions obtainable from each way of restricting it to a subset of n - - k variables. We show that the complexity of a ⁿ_3,5 function is no less than , and this bound cannot be much improved. Further, we find that for each k, there are ⁿ_k,2^k functions with complexity linear in n.     

Strong product of factor-critical graphs

Strong product G ₁? G ₂ of two graphs G ₁ and G ₂ has a vertex set V(G ₁)×V(G ₂) and two vertices (u ₁, v ₁) and (u ₂, v ₂) are adjacent whenever u ₁=u ₂ and v ₁ is adjacent to v ₂ or u ₁ is adjacent to u ₂ and v ₁=v ₂, or u ₁ is adjacent to u ₂ and v ₁ is adjacent to v ₂. We investigate the factor-criticality of G ₁? G ₂ and obtain the following. Let G ₁ and G ₂ be connected m-factor-critical and n-factor-critical graphs, respectively. Then i. if m? 0, n=0, |V(G ₁)|? 2m+2 and |V(G ₂)|? 4, then G ₁? G ₂ is (2m+2)-factor-critical;

ii. if n=1, |V(G ₁)|? 2m+3 and either m? 3 or |V(G ₂)|? 5, then G ₁? G ₂ is (2m+4??)-factor-critical, where ?=0 if m is even, otherwise ?=1;

iii. if m+2 ? |V(G ₁)|? 2m+2, or n+2? |V(G ₂)|? 2n+2, then G ₁? G ₂ is mn-factor-critical;

iv. if |V(G ₁)|? 2m+3 and |V(G ₂)|? 2n+3, then G ₁? G ₂ is (mn?min{[3m/2]₂, [3n/2]₂})-factor-critical.

     

L(2, 1)-labellings for direct products of a triangle and a cycle

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.     

AN ALGORITHM FOR FINDING ALL FUNCTIONS EMBEDDED IN A RELATION

The problem is posed: find an algorithm which for any given n-dimensional relation R ? A₁ × A₂ × ? × A_n, defined on a set family A = { A₁, A₂, ?, A_nrcub;, n = 1,2, ?, determines all functional dependences between disjoint subsets of A which are embedded in R. A solution algorithm is presented, a theorem is proved that allows a simplification in the algorithm, and an efficient computer implementation (available through the General Systems Depository) is demonstrated.     

Block Toeplitz matrices and preconditioning

We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT _n , withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T _n } are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L ², and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P _n ⁻¹ T_n}, where the sequence{P _n } is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP _n ⁻¹ T _n is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp ⁻¹ f. We also prove that the firstm eigenvalues ofP _n ⁻¹ T_n tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned matricesP _n ⁻¹ T_n are computed.     

An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(G_K), in 2-trees. Based on this result, we can also computeR(G_K) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.     

Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach.23, 566–571) is solved: lim_n→∞M(m, n)/n=log m/2+m/2^{log m}.     

寻找无向图中回路的并行算法

对无向简单图Ｇ＝（Ｖ，Ｅ），｜Ｖ｜＝ｎ，｜Ｅ｜＝ｍ，给出对下述问题的ＮＣ算法：（１）寻找Ｇ中最短回路；（２）寻找Ｇ中最短偶（奇）长度回路；（３）求解Ｃ_ｋ，ｋ＝３，４，这里Ｃ_ｋ表示Ｇ中长度为ｋ的回路．     

Conditional fault diagnosis of hierarchical hypercubes

The design of large dependable multiprocessor systems requires quick and precise mechanisms for detecting the faulty nodes. The system-level fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the hierarchical hypercube HHC _n when the number of faulty vertices is up to two or three times of the traditional connectivity. Based on this fault resiliency, we establish that the conditional diagnosability of HHC _n (n=2 ^m +m, m≥2) under the comparison model is 3m?2, which is about three times of the traditional diagnosability.