共查询到20条相似文献,搜索用时 31 毫秒
1.
We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=( V, E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N( v) of the destination v has at least k parent pointers. A capacity- k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V− N( v) can be partitioned into k nonempty classes labeled 1,2,…, k such that any set of sink trees T1, T2,…, Tk are pairwise independent, where tree Ti is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity- k acorn A, yielding a k-independent sink tree generating scheme. 相似文献
2.
This paper presents an efficient algorithm for enumerating all minimal a- b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = ( V, E), Our algorithm requires O( n3Rab) time, which improves the known result of O( n4Rab) time for solving this problem, where ¦ V¦= n and Rab is the number of minimal a- b separators. The algorithm can be generalized for enumerating all minimal A- B separators that separate non-adjacent vertex sets A, B < V, and it requires O( n2( n − nA − nb) RAB) time in this case, where na = ¦ A¦, nB = ¦ B¦ and rAB is the number of all minimal A− B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O( n3R+Σ + n4RΣ), which improves the known result of O( n6RΣ) time, where Rσ is the number of all minimal separators of G and RΣR+Σ = ∑ 1i, v j) ER vivj (n( n − 1)/2 − m) RΣ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O(( n/ log n) Rab) time and the second one runs in time O(( n/ log n) R+Σ+ n log nRΣ) on a CREW PRAM with O( n3) processors. 相似文献
3.
In Part I of this paper, a particular iterative method used in applied mechanics is shown to belong to a general class of methods termed SOR-Newton-( mk) iterative methods. The purpose here is to make a case study of the method and compare its performance with Newton iteration and Newton-SOR iteration. The numerical experiments are designed to examine the range of convergence of the mk = 1 step method, rates of convergence, and the effect of relaxation. 相似文献
4.
We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by − G/ rp + H/ rq. In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time tk = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations Fi,k = miai,k, I = 1, 2, 3, …, n, where mi is the mass of the ith particle. Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others. 相似文献
5.
The performance of a fuzzy k-NN rule depends on the number k and a fuzzy membership-array W[ l, mR], where l and mR denote the number of classes and the number of elements in the reference set XR respectively. The proposed learning procedure consists in iterative finding such k and W which minimize the error rate estimate by the leaving ‘leaving one out‘ method. 相似文献
6.
The nonlinear projection methods are minimization procedures for solving systems of nonlinear equations. They permit reevaluation of nk, 1 ≤ nk ≤ n, components of the approximate solution vector at each iteration step where n is the dimension of the system. At iteration step k, the reduction in the norm of the residue vector depends upon the nk components which are reevaluated. These nk components are obtained by solving a linear system. We present two algorithms for determining the components to be modified at each iteration of the nonlinear projection method and compare the use of these algorithms to Newton's method. The computational examples demonstrate that Newton's method, which reevaluates all components of the approximate solution vector at each iteration, can be accelerated by using the projection techniques. 相似文献
7.
For arbitrary equally sized square complex matrices A and Q ( Q Hermitian), the paper provides a complete algebraic test for verifying the existence of a Hermitian solution X of the nonstrict Lyapunov inequality A*X + XA + Q 0. If existing, we exhibit how to construct a solution. Our approach involves the validation problem for the linear matrix inequality Σ j=1k ( Aj*XjBj + Bj*Xj*Aj) + Q> 0 in Xj, for which we provide an algebraic solvability test and a construct solutions if the kernels of Aj or, dually, those of Bj form an isotonic sequence. 相似文献
8.
It is pointed out in this brief paper that the l1 optimization problem min Q ε lqp1 | H − U * Q * V | 1, H ε lmn1, U ε lmq1, V ε lpn1 can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case. 相似文献
9.
We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the ( i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let qe( m) be the smallest integer q satisfying Berlekamp’ s bound
. Then at least qe( m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly qe( m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly qe( m) questions—or equivalently, e-error correcting codes with 2 m codewords of length qe( m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe( m)− m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, qe( m)−1 questions do not suffice to find the unknown number, and qe( m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests. 相似文献
11.
Finite elements are used to estimate singularity powers for a crack tip perpendicularly terminating at a material interface. The influence of material stacking sequence upon singularity power estimates is considered as function of bond line width. The ratio of bond line elastic modulus ( E2) to that of the crack containing material ( E1) is used to define the various cases considered ( m = E2/ E1) The width of the bond line is found to have some influence upon singularity powers. It is found that for m < 1.0 the material stacking sequence has little effect upon singularity powers. Conversely, for m > 1.0 the material stacking sequence is found to have the most significant influence upon singularity powers as a function of bond line width. The variation of crack tip stresses for various material combinations and bond line widths is also considered. 相似文献
12.
In many calculations, spectral discretization in space is coupled with a standard ordinary differential equation formula in time. To analyze the stability of such a combination, one would like simply to test whether the eigenvalues of the spatial discretization operator (appropriately scaled by the time step k) lie in the stability region for the o.d.e. formula, but it is well known that this kind of analysis is in general invalid. In the present paper we rehabilitate the use of stability regions by proving that a discrete linear multistep ‘method of lines’ approximation to a partial differential equation is Lax-stable, within a small algebraic factor, if and only if all of the -pseudo-eigenvalues of the spatial discretization operator lie within O() of the stability region as → 0. An -pseudo-eigenvalue of a matrix A is any number that is an eigenvalue of some matrix A + E with E ; our arguments make use of resolvents and are closely related to the Kreiss matrix theorem. As an application of our general result, we show that an explicit N-point Chebyshev collocation approximation of ut = − xux on [−1, 1] is Lax-stable if and only if the time step satisfies k = O( N−2), although eigenvalue analysis would suggest a much weaker restriction of the form k CN−1. 相似文献
13.
Let x be an infinite word on a finite alphabet A. For each position n, the separator of x at n is the smallest factor of x which begins at index n and that does not appear before in x. Let Sx be the function such that Sx( n) is the length of the separator of x at index n if it exists and otherwise 0. We consider the problem of computing Sx in the case where x is generated by iterating a morphism σ : A* → A*. We prove the following theorem: 相似文献
14.
In this paper the problem of pole assignment using constant gain output feedback is studied for MIMO system with system order n > m + l − 1, where m and l are the number of inputs and outputs, respectively. A new procedure is presented to design a constant gain output feedback matrix which assigns ( m + l − 2) poles exactly to the desired locations and shifts all the unassigned poles to suitable locations using root locus techniques. 相似文献
15.
The iterative map xn+1 = rnxn (1 - xn) is investigated with rn changing periodically between two values A and B. Different periodicities are assumed, e.g., { rn} = { BABA …} or { rn} = { BBABA BBABA …}. The Lyapunov exponent (a measure of average stability) is displayed with high resolution on the A- B-plane. The resulting images have aesthetically appealing self-similar structures. Furthermore, these images allow with one glimpse the identification of a number of system properties: coexistence of attractors, superstable curves, order by alternation of chaotic processes, and chaos by periodic resetting from a stable into an unstable fixed point. 相似文献
16.
Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set { vii0} of (finite) words on A such that ƒ= v0v1… vi…, { vii1} is a biprefix code and vi≠ vj for positive integers i≠ j. 相似文献
17.
The computation of the generalised Inverse A+ of matrix A depends critically of the rank of A and involves several matrix multiplications. It is shown here that if A is of the form
where Ai are now vectors, then A+ can be computed efficiently and accurately by a simple algebraic method. 相似文献
18.
Butterflies are undirected graphs of bounded degree. They are widely used as interconnection networks. In this paper we study the feedback vertex set problem for butterflies. We show that the feedback vertex set found by Luccio's algorithm [Inform. Process. Lett. 66 (1998) 59–64] for the k-dimensional butterfly Bk is of size
. Besides, we propose an algorithm to find a feedback vertex set of size either
or
for Bk depending on whether k is even or odd. 相似文献
19.
The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in AC 1, the problems in LOGCFL are highly parallelizable. By results of Ruzzo (JCSS 21 (1980) 218), the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM M recognizing a language A in LOGCFL, it is possible to construct an LLOGCFL transducer TM such that TM on input w A outputs an accepting tree for M on w. It follows that computing single LOGCFL certificates is feasible in functional AC1 and is thus highly parallelizable. Wanke (J. Algorithms 16 (1994) 470) has recently shown that for any fixed k, deciding whether the treewidth of a graph is at most k is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in AC1. We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an m-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width. 相似文献
20.
The inflation GI of a graph G with n( G) vertices and m( G) edges is obtained from G by replacing every vertex of degree d of G by a clique Kd. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ p( G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ( G)2, then n( G)γ p( GI)4 m( G)/[δ( G)+1], and the equality γ p( GI) = n( G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree. 相似文献
|