共查询到20条相似文献,搜索用时 15 毫秒
1.
Tsutomu Anazawa 《International Transactions in Operational Research》2001,8(3):259-268
The paper considers a generalization of the optimum requirement spanning tree problem (ORST problem) first studied by Hu in 1974. Originally, ORST was regarded as a communication network of tree type with the minimum average cost, and it is obtained by the well-known Gomory–Hu algorithm when the degrees of vertices are not restricted. The ORST problem is generalized by (i) generalizing the objective function and (ii) imposing maximum degree constraints. The generalized ORST problem includes some practical problems, one of which is proposed in this paper, but is not efficiently solvable in general. However, I show that a particular tree (which is obtained by a sort of greedy algorithm but is explicitly definable) is a solution of the generalized problem when a certain practical condition is satisfied. The condition is closely related to the Monge property, which is originally discussed in the Hitchcock transportation problem, and is known to make some NP-hard problems efficiently solvable. 相似文献
2.
Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting)
intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum
cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the
general case of the problem, our algorithms compute a maximum matching in O( log
3
n) time using O(n/ log
2
n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings
among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping
intervals in proper interval graphs.
Received November 20, 1995; revised September 3, 1998. 相似文献
3.
4.
基于可重构模拟细胞阵列的进化电路研究 总被引:4,自引:3,他引:1
进化电路具有自组织、自适应和自修复的特性,在航空航天领域具有重大应用价值;阐述了模拟可进化电路的基本原理,分析了基于现场可编程晶体管细胞阵列FPTA(Field Programmable Transistor Array)的可进化模拟电路体系结构与电路原理,提出了基于单染色体进化策略的模拟细胞阵列进化方法;建立了FPTA细胞电路的数学仿真模型,开发了模拟细胞电路进化研究仿真平台;以带通滤波器电路作为进化实例,讨论了进化实验结果,实验结果表明:新型FPTA细胞阵列电路能够通过进化得到带通滤波器电路,所设计的细胞电路是正确的,进化方案是有效的. 相似文献
5.
广义预测控制的并行算法 总被引:4,自引:0,他引:4
研究广义预测控制(GPC)的并行算法.常规对GPC的设计,面临的在线矩阵求逆的耗时和控制灵活性的矛盾很难较好的解决.本文通过在线并行实现,有效地提高了算法的实时性和对复杂对象的适应性. 相似文献
6.
Consider the following NP-hard problems: Given a graph G , find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G . Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced [6],[10].
The approximation factors are improved from 2 to 3/2 for both of the problems. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar
progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε for these two problems without computing depth-first-search trees.
Received June 21, 1995; revised December 24, 1996, and June 2, 1997. 相似文献
7.
We study a problem of scheduling n independent parallel jobs on hypercubes. A parallel job is required to be scheduled on a subcube of processors. All jobs are available at the beginning, each of which is associated with a due date. The objective is to maximize the total number of early jobs. We provide an optimal polynomial time algorithm for the unit processing time job system. 相似文献
8.
In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs.
Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing
tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems
on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can
be stated in monadic second-order logic.
Received July 15, 1997; revised January 29, 1999, and June 23, 1999. 相似文献
9.
In the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature.
This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix
computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and
no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper
we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically
brilliant solutions fail the severe test of the ``Engineering of Algorithms.' We perform a comparative analysis of several
well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that,
for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting
no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the
only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required
to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed
instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly
adequate for the fixed-precision approach.
Received March 28, 1998; revised February 2, 1999, and April 21, 1999. 相似文献
10.
E. Ruppert 《Algorithmica》2000,28(2):242-254
A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are
allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+nk log
2
k) work and O( log^3k log ^*k+ log n( log log k+ log ^*n)) time, assuming that a shortest path tree rooted at the destination is pre-computed. The paths themselves can be extracted
from the implicit representation in O( log k + log n) time, and O(n log n +L) work, where L is the total length of the output.
Received July 2, 1997; revised June 18, 1998. 相似文献
11.
This paper presents several algorithms for solving problems using massively parallel SIMD hypercube and shuffle-exchange computers. The algorithms solve a wide variety of problems, but they are related because they all use a common strategy. Specifically, all of the algorithms use a divide-and-conquer approach to solve a problem withN inputs using a parallel computer withP processors. The structural properties of the problem are exploited to assure that fewer thanN data items are communicated during the division and combination steps of the divide-and-conquer algorithm. This reduction in the amount of data that must be communicated is central to the efficiency of the algorithm.This paper addresses four problems, namely the multiple-prefix, data-dependent parallel-prefix, image-component-labeling, and closest-pair problems. The algorithms presented for the data-dependent parallel-prefix and closest-pair problems are the fastest known whenN P and the algorithms for the multiple-prefix and image-component-labeling problems are the fastest known whenN is sufficiently large with respect toP.This work was supported in part by our NSF Graduate Fellowship. 相似文献
12.
Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem
is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, ó'Dúnlaing, and Yap, which runs in
O( log
2
n) time using O(n) processors. We obtain this result by using a new ``two-stage' random sampling technique. By choosing large samples in the
first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up' that is typical in recursive parallel geometric
algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm.
This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel
algorithms for this problem use the transformation to three-dimensional half-space intersection). 相似文献
13.
Abstract. A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it.
We study the problem of scheduling a set of n independent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed
ε > 0 , computes in O(n) time a non-preemptive schedule of length at most (1+ε) times the optimum. 相似文献
14.
The problem of finding a sublogarithmic time optimal parallel algorithm for 3 -colouring rooted forests has been open for long. We settle this problem by obtaining an O(( log log n) log
*
( log
*
n)) time optimal parallel algorithm on a TOLERANT Concurrent Read Concurrent Write (CRCW) Parallel Random Access Machine (PRAM).
Furthermore, we show that if f(n) is the running time of the best known algorithm for 3 -colouring a rooted forest on a COMMON or TOLERANT CRCW PRAM, a fractional independent set of the rooted forest can be found
in O(f(n)) time with the same number of processors, on the same model.
Using these results, it is shown that decomposable top-down algebraic computation and, hence, depth computation (ranking),
2 -colouring and prefix summation on rooted forests can be done in O( log n) optimal time on a TOLERANT CRCW PRAM.
These algorithms have been obtained by proving a result of independent interest, one concerning the self-simulation property
of TOLERANT: an N -processor TOLERANT CRCW PRAM that uses an address space of size O(N) only, can be simulated on an n -processor TOLERANT PRAM in O(N/n) time, with no asymptotic increase in space or cost, when n=O(N/ log log N) .
Received May 20, 1997; revised June 15, 1998. 相似文献
15.
Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem
remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n
2
) processors on an EREW PRAM.
Received July 3, 1995; revised April 1, 1996. 相似文献
16.
17.
In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree,
(3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction
and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity
and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) .
The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p
ε
, for some fixed ε > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time.
It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due
to the considerable protocol overhead associated with each message transmission, this is an important property. The result
for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the
first practically relevant parallel algorithms for these standard graph problems.
Received July 5, 2000; revised April 16, 2001. 相似文献
18.
Abstract. External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory
of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation.
In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited
success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge
by the ACM Working Group on Storage I/ O for Large-Scale Computing.
In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors
on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine.
When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems. 相似文献
19.