共查询到20条相似文献,搜索用时 624 毫秒
1.
The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E
G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College. 相似文献
2.
Raymond Greenlaw 《Theory of Computing Systems》1992,25(3):161-175
Several classes of sequential algorithms to approximate themaximum acyclic subgraph problem are examined. The equivalentfeedback arc set problem isNP-complete and there are only a few classes of graphs for which it is known to be inP. Thus, approximation algorithms are very important for this problem. Our goal is to determine how effectively the various sequential algorithms parallelize. Of the sequential algorithms we study, natural decision problems based on several of them are provedP-complete. Parallel implementations usingO(log ¦V¦) time and ¦E¦ processors on an EREW PRAM exist for the other algorithms. Interestingly, the parallelizable algorithms appear very similar to some of theinherently sequential algorithms. Thus, for approximating the maximum acyclic subgraph problem small algorithmic changes drastically alter parallel complexity, unlessNC equalsP. 相似文献
3.
《国际计算机数学杂志》2012,89(9):1490-1497
Let G be a connected graph. A spanning tree T of G is a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. If their distances in T and G differ by at most t, then T is an additive tree t-spanner of G. In this paper, we show that any permutation graph has an additive tree 2-spanner, and it can be found in O(n) time sequentially or in O(log n) time with O(n/log n) processors on the EREW PRAM computational model by using a previously published algorithm for finding a tree 3-spanner of a permutation graph. 相似文献
4.
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. 相似文献
5.
In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log2
n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM. 相似文献
6.
We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary
permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM.
The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n
1+o(1)
) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem.
On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs.
The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation
and then to simulate this network on the PRAM model in a fast way.
Received November 1996; revised March 1997. 相似文献
7.
8.
Pei-Chi Huang Hsin-Wen Wei Wan-Chen Lu Wei-Kuan Shih Tsan-sheng Hsu 《Algorithmica》2009,54(3):353-378
This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem,
is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e.,
bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical
data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding
edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not
such an augmentation is possible.
We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure
for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first
augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem.
H.-W. Wei, W.-C. Lu and T.-s. Hsu research supported in part by NSC of Taiwan Grants 94-2213-E-001-014, 95-2221-E-001-004
and 96-2221-E-001-004. 相似文献
9.
Ka Wong Chong Stavros D. Nikolopoulos Leonidas Palios 《Theory of Computing Systems》2004,37(4):527-546
In this paper we consider the problem of computing
the connected components of the complement of a given graph.
We describe a simple sequential algorithm for this problem,
which works on the input graph and not on its complement,
and which for a graph on n vertices and m edges
runs in optimal O(n+m) time.
Moreover, unlike previous linear co-connectivity algorithms,
this algorithm admits efficient parallelization, leading to
an optimal O(log n)-time and O((n+m)log n)-processor
algorithm on the EREW PRAM model of computation.
It is worth noting that, for the related problem
of computing the connected components of a graph, no optimal
deterministic parallel algorithm is currently available.
The co-connectivity algorithms find applications in
a number of problems.
In fact, we also include a parallel recognition algorithm
for weakly triangulated graphs, which takes advantage of
the parallel co-connectivity algorithm and achieves
an O(log2 n) time complexity using
O((n+m2) log n) processors on the EREW PRAM model of computation. 相似文献
10.
A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR
gates. A layered PMC is a PMC in which all input nodes are in the external face, and the gates can be assigned to layers in
such a way that every wire goes between gates in successive layers. Goldschlager, Cook and Dymond, and others have developed
NC
2
algorithms to evaluate a layered PMC when the output node is in the same face as the input nodes. These algorithms require
a large number of processors (Ω(n
6
), where n is the size of the input circuit).
In this paper we give an efficient parallel algorithm that evaluates a layered PMC of size n in time using only a linear number of processors on an EREW PRAM. Our parallel algorithm is the best possible to within a polylog
factor, and is a substantial improvement over the earlier algorithms for the problem.
Received April 18, 1994; revised April 7, 1995. 相似文献
11.
《国际计算机数学杂志》2012,89(1):59-70
In this paper, a parallel algorithm is presented to find all cut-vertices and blocks of an interval graph. If the list of sorted end points of the intervals of an interval graph is given then the proposed algorithm takes O(log n) time and O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n). 相似文献
12.
For a positive integer c, a c-vertex-ranking of a graph G=(V,E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O(log2n) time using linear number of operations on the EREW PRAM model. 相似文献
13.
Vicky Choi 《Quantum Information Processing》2011,10(3):343-353
In Choi (Quantum Inf Process, 7:193–209, 2008), we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design
problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate
an optimal complete-graph-minor hardware graph. Given a family F{\mathcal{F}} of graphs, a (host) graph U is called F{\mathcal{F}}-minor-universal if for each graph G in F, U{\mathcal{F}, U} contains a minor-embedding of G. The problem for designing a F{{\mathcal{F}}}-minor-universal hardware graph U
sparse
in which F{{\mathcal{F}}} consists of a family of sparse graphs (e.g., bounded degree graphs) is open. 相似文献
14.
Chin-Wen Ho Sun-Yuan Hsieh Gen-Huey Chen 《Journal of Parallel and Distributed Computing》1998,51(2):407
In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(GK), in 2-trees. Based on this result, we can also computeR(GK) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time. 相似文献
15.
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n -vertex graph the algorithm runs in o(( log n)
1+
ɛ
) expected time for any ɛ >0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem.
This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation—the
QSM and the BSP. 相似文献
16.
《Journal of Parallel and Distributed Computing》1995,26(1):116-124
In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs. 相似文献
17.
In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log2 n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM. 相似文献
18.
《Information Processing Letters》1987,25(4):241-245
This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of Δ using Δ + 1 colors and for finding a maximal independent set in a constant-degree graph. Given a graph with n vertices, the algorithms run in O(lg1n) time on an EREW PRAM with O(n) processors. The algorithms use only local communication and achieve the same complexity bounds when implemented in a distributed model of parallel computation. 相似文献
19.
《Journal of Parallel and Distributed Computing》1995,24(1):94-99
We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors. 相似文献
20.
According to Cayley's tree formula, there are n
n-2
labelled trees on n vertices. Prüfer gave a bijection between the set of labelled trees on n vertices and sequences of n-2 numbers, each in the range 1, 2, ..., n . Such a number sequence is called a Prüfer code. The straightforward implementation of his bijection takes O(n log n ) time. In this paper we propose an O(n) time algorithm for the same problem. Our algorithm can be easily parallelized so that a Prüfer code can be generated in
O (log n ) time using O(n) processors on the EREW PRAM computational model.
Received October 2, 1998, and in final form March 1, 1999. 相似文献