Let K be contained in the vertex-set of a graph G. ''The most vital edge'' is the edge whose deletion yields the largest decrease in the K-terminal reliability, that is the probability that all vertice...
详细信息
Let K be contained in the vertex-set of a graph G. ''The most vital edge'' is the edge whose deletion yields the largest decrease in the K-terminal reliability, that is the probability that all vertices in K are connected. In this paper, we present a linear-time algorithm for finding the most vital edge with respect to K-terminal reliability in series-parallel networks.
The notion of orthonormal wavelet packets introduced by Coifman and Meyer is generalized to the nonorthogonal setting in order to include compactly supported and symmetric basis functions. In particular, dual (or bior...
详细信息
The notion of orthonormal wavelet packets introduced by Coifman and Meyer is generalized to the nonorthogonal setting in order to include compactly supported and symmetric basis functions. In particular, dual (or biorthogonal) wavelet packets are investigated and a stability result is established. algorithms for implementations are also developed.
The rectilinear Steiner ratio is the worst-case ratio of the length of a rectilinear minimum spanning tree to the length of a rectilinear Steiner minimal tree. Hwang proved that the ratio for point sets in the plane i...
详细信息
The rectilinear Steiner ratio is the worst-case ratio of the length of a rectilinear minimum spanning tree to the length of a rectilinear Steiner minimal tree. Hwang proved that the ratio for point sets in the plane is 3/2. We provide a simple proof of the 3/2-bound.
A dual ascent algorithm is described for the 1-tree relaxation of the symmetric traveling salesman problem. The ascent directions correspond to increasing (decreasing) the dual variables for the nodes of a set that is...
详细信息
A dual ascent algorithm is described for the 1-tree relaxation of the symmetric traveling salesman problem. The ascent directions correspond to increasing (decreasing) the dual variables for the nodes of a set that is out of kilter high (low) for all 1-trees that are optimal at the current dual solution. This algorithm is shown to obtain near optimal bounds in about one-quarter of the time required by the subgradient method on a sample of well-known test cases.
A new reconfigurable systolic multicomputer architecture is presented. The proposed architecture, called the Cylindrical Banyan Multicomputer (CBM), is based on the structure of a modified banyan network where every n...
详细信息
A new reconfigurable systolic multicomputer architecture is presented. The proposed architecture, called the Cylindrical Banyan Multicomputer (CBM), is based on the structure of a modified banyan network where every node of the network graph is composed of an application processor, a local memory and a communication processor, and network's inputs and outputs are merged (fused). The CBM has one of the lowest (cost) X (delay) among known multicomputer architectures based on regular networks. It is shown that a variety of computation structures such as pipelines, rings, and trees may be constructed and reconfigured in an optimal or a nearby optimal way on the CBM architecture, and that various basic algorithms can be executed very efficiently in a systolic manner. It is also shown that the CBM is an easily diagnosable and fault-tolerant system.
The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P1 and P2. If P is a mixture of two (approximate...
详细信息
The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P1 and P2. If P is a mixture of two (approximately) Gaussian subpopulations, then P1 and P2 are good approximations to the original Gaussians, if their Fisher distance is great enough. Moreover, good approximations to P1 and P2 can be obtained by dividing P into small parts; finding the maximum-distance (MD) subdivision of each part; combining small groups of these subdivisions into (approximate) MD subdivisions of larger parts; and so on. This divide-and-conquer approach yields an approximate MD subdivision of P in O(log n) computational steps using O(n) processors, where n is the size of P.
trees, and particularly binary trees, appear frequently in the classification literature. When studying the properties of the procedures that fit trees to sets of data, direct analysis can be too difficult, and Monte ...
详细信息
trees, and particularly binary trees, appear frequently in the classification literature. When studying the properties of the procedures that fit trees to sets of data, direct analysis can be too difficult, and Monte Carlo simulations may be necessary, requiring the implementation of algorithms for the generation of certain families of trees at random. In the present paper we use the properties of Prufer's enumeration of the set of completely labeled trees to obtain algorithms for the generation of completely labeled, as well as terminally labeled t-ary (and in particular binary) trees at random, i.e., with uniform distribution. Actually, these algorithms are general in that they can be used to generate random trees from any family that can be characterized in terms of the node degrees. The algorithms presented here are as fast as (in the case of terminally labeled trees) or faster than (in the case of completely labeled trees) any other existing procedure, and the memory requirements are minimal. Another advantage over existing algorithms is that there is no need to store pre-calculated tables.
We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space...
详细信息
We consider the following problem. Suppose a rooted treeT is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm that enables us to answer each query in $O(1)$ time, as in Harel and Tarjan [SIAM J. Comput., 13 (1984), pp. 338–355]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in $O(1)$ time using a single processor.
We present a Turbo Pascal implementation of the expanding equilibrium algorithm for linear, single commodity spatial price equilibrium problems. We provide evidence that our microcomputer implementation is faster than...
详细信息
We present a Turbo Pascal implementation of the expanding equilibrium algorithm for linear, single commodity spatial price equilibrium problems. We provide evidence that our microcomputer implementation is faster than a mainframe implementation of a widely-referenced alternative algorithm. An executable version of our program, with documentation, is available upon request.
The empirical performance of the algorithms of Kruskal, Prim, and Sollin for determining a minimum spanning tree is examined and found to be considerably better than suggested by worst case analysis. Kruskal's alg...
详细信息
The empirical performance of the algorithms of Kruskal, Prim, and Sollin for determining a minimum spanning tree is examined and found to be considerably better than suggested by worst case analysis. Kruskal's algorithm is generally slowest, with the Prim algorithm being preferred for dense networks and the Sollin algorithm for sparse networks. A simple criterion in terms of the number of vertices and edges of a network is given which indicates which of the Prim or Sollin algorithms as implemented is faster for a particular problem.
暂无评论