共查询到20条相似文献,搜索用时 15 毫秒
1.
Bampis E. Elhaddad M. Manoussakis Y. Santha M. 《Journal of Algorithms in Cognition, Informatics and Logic》1995,19(3)
We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n2/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n2/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n2/log n) processors in the CRCW model and in time O(log2n) with O(n2/log n log log n) processors in the EREW model. 相似文献
2.
We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk2(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk2log2n). 相似文献
3.
The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n˙ Log (n)) execution time, may give an O(n˙n˙ Log (n)) to peel all the set; an O(n˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n˙n) performance. 相似文献
4.
Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs 总被引:1,自引:0,他引:1
We give a direct combinatorial O(n3logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n5) and O(n4) dynamic programming algorithms for this problem. 相似文献
5.
Marek Chrobak Leszek G
sieniec Wojciech Rytter 《Journal of Algorithms in Cognition, Informatics and Logic》2002,43(2):177
We establish an O(nlog2n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2log2n) algorithm for gossiping in the same network model. 相似文献
6.
In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log2
n) time usingO(n
3/logn) processors on the CREW PRAM, orO(logn) time usingO(n
3) processors on the CRCW PRAM. 相似文献
7.
We present an O(n2) algorithm for finding a specified oriented path of order at least n in a tournament of order n. Using this algorithm, we present an O(n2) algorithm that finds a specified oriented path from a given vertex if one exists. 相似文献
8.
Jin Kue Wong 《BIT Numerical Mathematics》1979,19(3):418-424
Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n
4) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n
3) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant. 相似文献
9.
Jesper Makholm Byskov Bolette Ammitzbll Madsen Bjarke Skjernaa 《Journal of Graph Theory》2005,48(2):127-132
We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105n/10 ≈ 1.5926n; such subgraphs show an upper bound of O(12n/4) = O(1.8613n) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005 相似文献
10.
A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)2) whenO(n
2.81/logn) processors are used. 相似文献
11.
Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n2 log2n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(logm/n log nn)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(nε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n). 相似文献
12.
Kurt C. Foster Stephen Q. Muth John J. Potterat Richard B. Rothenberg 《Computational & Mathematical Organization Theory》2001,7(4):275-285
A new graph theoretical algorithm to calculate Katz status scores reduces computational complexity from time O(n
3) to O(n + m). Randomly-generated graphs as well as data from a large empiric study are used to test the performance of two commercial network analysis packages (GRADAP and UCINET V), compared to the performance achieved by the authors' algorithm, implemented in Visual Basic. 相似文献
13.
Baruch Awerbuch Bonnie Berger Lenore Cowen David Peleg 《Random Structures and Algorithms》1994,5(3):441-452
We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log5(n)) time, and uses O(n2) processors. © 1994 John Wiley & Sons, Inc. 相似文献
14.
R.A.CUNINGHAME-GREEN LINYIXUN 《高校应用数学学报(英文版)》1996,11(2):225-234
Abstract. Computing the maximum cycle-mean of a weighted digraph is relevant to a number of applications, and combinatorial algorlthnls of complexity 0(n) are known.We present a new algorithm, with computational evidence to suggest an expected run-time growth rate below O(n^3) 相似文献
15.
Hillel Gazit John H Reif 《Journal of Algorithms in Cognition, Informatics and Logic》1998,28(2):290-314
We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log2 n) time withn1 + εprocessors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton3/2 + ε, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn4randomized processors orn5deterministic processors. 相似文献
16.
Applications of random sampling in computational geometry,II 总被引:10,自引:0,他引:10
We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE
d
inO(n logn) expected time ford=3, andO(n
[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE
3 inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE
3. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE
3, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams. 相似文献
17.
《Journal of computational and graphical statistics》2013,22(2):352-362
This article considers computational aspects of the nonparametric maximum likelihood estimator (NPMLE) for the distribution function of bivariate interval-censored data. The computation of the NPMLE consists of a parameter reduction step and an optimization step. This article focuses on the reduction step and introduces two new reduction algorithms: the Tree algorithm and the HeightMap algorithm. The Tree algorithm is mentioned only briefly. The HeightMap algorithm is discussed in detail and also given in pseudo code. It is a fast and simple algorithm of time complexityO(n2). This is an order faster than the best known algorithm thus far by Bogaerts and Lesaffre. We compare the new algorithms to earlier algorithms in a simulation study, and demonstrate that the new algorithms are significantly faster. Finally, we discuss how the HeightMap algorithm can be generalized to d-dimensional data with d > 2. Such a multivariate version of the HeightMap algorithm has time complexity O(nd). 相似文献
18.
Danny Z. Chen 《Journal of Algorithms in Cognition, Informatics and Logic》1996,20(3):459-478
Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n2) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear. 相似文献
19.
Franz Aurenhammer 《Discrete and Computational Geometry》1990,5(1):243-254
A new duality between order-k Voronoi diagrams inE
d and convex hulls inE
d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k
2
n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung. 相似文献
20.
Cao An Wang 《BIT Numerical Mathematics》1991,31(2):230-236
An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n
2) algorithms.The work was supported by NSERC grant OPG0041629. 相似文献