Results 301 to 310 of about 36,225 (338)
Some of the next articles are maybe not open access.
Simple learning algorithms using divide and conquer
Computational Complexity, 1995zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
Tree machines and divide-and-conquer algorithms
2007A tree machine consists of a number of processors (each with its own memory) mutually connected via communication branches so as to form a binary tree. Two processors may communicate only via a common communication link. Such a tree machine is a completely general, concurrent processing engine and can be used for problems decomposed in a hierarchical ...
openaire +2 more sources
An Efficient Multibody Divide and Conquer Algorithm
Volume 6: 5th International Conference on Multibody Systems, Nonlinear Dynamics, and Control, Parts A, B, and C, 2005A new and efficient form of Featherstone’s multibody Divide and Conquer Algorithm (DCA) is presented. The DCA was the first algorithm to achieve theoretically optimal logarithmic time complexity with a theoretical minimum of parallel computer resources for general problems of multibody dynamics, however the DCA is extremely inefficient in the presence ...
openaire +1 more source
Divide-and-conquer approximation algorithms via spreading metrics
Proceedings of IEEE 36th Annual Foundations of Computer Science, 2000We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time.
Guy Even +3 more
openaire +1 more source
A divide-and-conquer algorithm for grid generation
Applied Numerical Mathematics, 1994The algorithm proposed here generates grid points in plane domains with four smooth boundary curves. It is similar to what one does instinctively when asked to generate a grid when given only the boundary: an algorithm starts with the initial boundary curves and fills in the interior grids, one curve at a time.
Dougherty, Randall L., Hyman, James M.
openaire +2 more sources
Engineering the Divide-and-Conquer Closest Pair Algorithm
Journal of Computer Science and Technology, 2007We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O(n log n) time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.'s bound of (3n log n)/2 Euclidean distances.
Minghui Jiang, Joel Gillespie
openaire +1 more source
Divide-and-Conquer Approximation Algorithm for Vertex Cover
SIAM Journal on Discrete Mathematics, 2009The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is $2-o(1)$. In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of $\frac{3}{2}$, to find approximate vertex covers for a large collection of randomly generated graphs and test ...
Eyjólfur Ingi Ásgeirsson, Cliff Stein
openaire +1 more source
Fast broadcast by the divide-and-conquer algorithm
2004 IEEE International Conference on Cluster Computing (IEEE Cat. No.04EX935), 2005Collective communication functions including the broadcast in cluster computers usually take O(m log P) time in propagating the size-m message to P processors. We have devised a new O(m) broadcast algorithm, independent of the number of processors involved, by using divided-and-conquer algorithm. Details are given below.
null Dongyoung Kim, null Dongseung Kim
openaire +1 more source
A Stable Divide and Conquer Algorithm for the Unitary Eigenproblem
SIAM Journal on Matrix Analysis and Applications, 2003A divide and conquer algorithm is introduced for computing the eigendecomposition of unitary upper Hessenberg matrices with a stable backward method. Numerical experiments illustrate the efficiency of the algorithm.
Gu, Ming +3 more
openaire +2 more sources
Divide-and-conquer algorithms on two-dimensional meshes
1998The Reflecting and Growing mappings have been proposed to map parallel divide-and-conquer algorithms onto two — dimensional meshes. The performance of these mappings has been previously analyzed under the assumption that the parallel algorithm is initiated always at the same fixed node of the mesh.
Miguel Valero-García +3 more
openaire +1 more source