The Depth First Search (DFS) algorithm is one of the basic techniques that is used in a very large variety of graph algorithms. Most applications of the DFS involve the construction of a depth-first spanning tree (DFS...
详细信息
The Depth First Search (DFS) algorithm is one of the basic techniques that is used in a very large variety of graph algorithms. Most applications of the DFS involve the construction of a depth-first spanning tree (DFS tree). In this paper, we give a complete characterization of all the graphs in which every spanning tree is a DFS tree. These graphs are called Total-DFS-Graphs. We prove that Total-DFS-Graphs are closed under miners. it follows by the work of Robertson and Seymour on graph miners that there is a finite set of forbidden miners of these graphs and that there is a polynomial algorithm for their recognition. We also provide explicit characterizations of these graphs in terms of forbidden miners and forbidden topological miners. The complete characterization implies explicit linear algorithm for their recognition. In some problems the degree of some vertices in the DFS tree obtained in a certain run are crucial and therefore we also consider the following problem: Let G=(V, E) be a connected undirected graph where \V\ = n and let d is an element of N-n be a degree sequence upper bound vector. Is there any DFS tree T with degree sequence d(T) that violates d (i.e., d(T) not less than or equal to d, which means:,There Exists j such that d(T)(j) > d(j))? We show that this problem is NP-complete even for the case where we restrict the degree of only on specific vertex to be less than or equal to k for a fixed k greater than or equal to 2 (i.e., d = (n - 1,..., n - 1, k, n - 1,..., n - 1)). (C) 1995 John Wiley & Sons, Inc.
The value of high-throughput genomic research is dramatically enhanced by association with key patient data. These data are generally available but of disparate quality and not typically directly associated. A system ...
详细信息
The value of high-throughput genomic research is dramatically enhanced by association with key patient data. These data are generally available but of disparate quality and not typically directly associated. A system that could bring these disparate data sources into a common resource connected with functional genomic data would be tremendously advantageous. However, the integration of clinical and accurate interpretation of the generated functional genomic data requires the development of information management systems capable of effectively capturing the data as well as tools to make that data accessible to the laboratory scientist or to the clinician. In this review these challenges and current information technology solutions associated with the management, storage and analysis of high-throughput data are highlighted. It is suggested that the development of a pharmacogenomic data management system which integrates public and proprietary databases, clinical datasets, and data mining tools embedded in a high-performance computing environment should include the following components: parallel processing systems, storage technologies, network technologies, databases and database management systems (DBMS), and application services.
We have developed algorithms to count singular values of a real bidiagonal matrix which are greater than a specified value. This requires the transformation of the singular value problem to an equivalent symmetric eig...
详细信息
We have developed algorithms to count singular values of a real bidiagonal matrix which are greater than a specified value. This requires the transformation of the singular value problem to an equivalent symmetric eigenvalue problem. The counting of singular values is paramount in the design of bisection- and multisection-type algorithms for computing singular values on serial and parallel machines. The algorithms are based on the eigenvalues of BBt, (BB)-B-t, and the 2n x 2n zero-diagonal tridiagonal matrix which is permutationally equivalent to the Jordan{Wielandt form [GRAPHICS] where B is an n x n bidiagonal matrix. The two product matrices, which do not have to be formed explicitly, lead to the progressive and stationary qd algorithms of Rutishauser. The algorithm based on the zero-diagonal matrix, which we have named the Golub-Kahan form, may be considered as a combination of both the progressive and stationary qd algorithms. We study important properties such as the backward error analysis, the monotonicity of the inertia count and the scaling of data which guarantee the accuracy and integrity of these algorithms. For high relative accuracy of tiny singular values, the algorithm based on the Golub-Kahan form is the best choice. However, if such accuracy is not required or requested, the differential progressive and differential stationary qd algorithms with certain modifications are adequate and more efficient. We also show how to transform the real skew-symmetric tridiagonal eigenvalue problem to a real bidiagonal singular value problem. Thus, the eigenvalues of a skew-symmetric matrix can be readily counted using algorithms developed here for bidiagonal matrices.
An earlier suggested parallel "ring" algorithm for solving the spatially onedimensional initial-boundary-value problem (IBVP) for a parabolic equation using an explicit difference method is shortly described...
详细信息
An earlier suggested parallel "ring" algorithm for solving the spatially onedimensional initial-boundary-value problem (IBVP) for a parabolic equation using an explicit difference method is shortly described. Theoretical estimates for both of the speed-up function and the communication complexity of this parallel algorithm are studied. The speed-up function is determined as the ratio between times for realization of the algorithm in sequentional and parallel cases. Theoretical estimates of the speed-up function show the significant speed-up of the parallel algorithm in comparison with the serial one for a large number of values computed by one processor during one time level and it is shown that the the speed-up tends to the number of used processors. Communication complexity is determined as a ratio between the number of interchanges and the number of arithmetical operations. It has been proven that the coefficient of the communication complexity for spatially m-dimensional IBVP tends in general to 3/4.
The main result of this paper is an effective count for Apollonian circle packings that are either bounded or contain two parallel lines. We obtain this by proving an effective equidistribution of closed horospheres i...
详细信息
The main result of this paper is an effective count for Apollonian circle packings that are either bounded or contain two parallel lines. We obtain this by proving an effective equidistribution of closed horospheres in the unit tangent bundle of a geometrically finite hyperbolic 3-manifold, whose fundamental group has critical exponent bigger than 1. We also discuss applications to affine sieves. Analogous results for surfaces are treated as well.
The evaluation of a domain integral is the dominant bottleneck in the numerical solution of viscous flow problems by vorticity methods, which otherwise demonstrate distinct advantages over primitive variable methods. ...
详细信息
The evaluation of a domain integral is the dominant bottleneck in the numerical solution of viscous flow problems by vorticity methods, which otherwise demonstrate distinct advantages over primitive variable methods. By applying a Bames-Hut multipole acceleration technique, the operation count for the integration is reduced from O(N-2) to O(N log N), while the memory requirements are reduced from O(N-2) to O(N). The algorithmic parameters that are necessary to achieve such scaling are described. The parallelization of the algorithm is crucial if the method is to be applied to realistic problems. A parallelization procedure which achieves almost perfect scaling is shown. Finally, numerical experiments on a driven cavity benchmark problem are performed. The actual increase in performance and reduction in storage requirements match theoretical predictions well, and the scalability of the procedure is very good. Copyright (C) 2003 John Wiley Sons, Ltd.
This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in po...
详细信息
This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.
Implementations of various fast Fourier transform (FFT) algorithms are presented for distributed-memory multiprocessors. These algorithms use data redistribution to localize the computation. The goal is to optimize co...
详细信息
Implementations of various fast Fourier transform (FFT) algorithms are presented for distributed-memory multiprocessors. These algorithms use data redistribution to localize the computation. The goal is to optimize communication cost by using a minimum number of redistribution steps. Both analytical and experimental performance results on the Intel iPSC/860 system are presented.
We define series/parallel/2-sum connections of two oriented matroids in terms of various axiom systems and an oriented modular join and sum operation by means of signed cocircuits and covectors. (C) 2011 Elsevier Ltd....
详细信息
We define series/parallel/2-sum connections of two oriented matroids in terms of various axiom systems and an oriented modular join and sum operation by means of signed cocircuits and covectors. (C) 2011 Elsevier Ltd. All rights reserved.
作者：
ZAKHAROV, VCERN
DIV DATA HANDLING CH-1211 GENEVA 23 SWITZERLAND
Modern computing, as well as the historical development of computing, has been dominated by sequential monoprocessing. Yet there is the alternative of parallelism, where several processes may be in concurrent executio...
详细信息
Modern computing, as well as the historical development of computing, has been dominated by sequential monoprocessing. Yet there is the alternative of parallelism, where several processes may be in concurrent execution. This alternative is discussed, in which the main developments involving parallelism are considered both from the standpoint of computing systems and that of applications than can exploit such systems. The account seeks to treat parallelism in a historical context, and to identify all the main aspects of concurrency in computation right up to the present time. The review includes a discussion both of parallel computer architectures and functional units as components in these architectures. The important question of limitations in concurrency is considered, and there is an account of typical numerical problems which contain parallelism, as well as languages appropriate to code these problems. Included will be a brief consideration of what use parallelism might be In the field of data processing.
暂无评论