For a weighted, undirected graph G = (V,E), the single most vital edge in a network with respect to shortest paths is the edge that, when removed, results in the greatest increase in the shortest distance between two ...
详细信息
For a weighted, undirected graph G = (V,E), the single most vital edge in a network with respect to shortest paths is the edge that, when removed, results in the greatest increase in the shortest distance between two nodes s and t. We give a sequential algorithm for the Single Most Vital Edge problem on weighted and undirected graphs. Our algorithm has a time complexity O(m alpha(m,n)), where n = /V/, m=/E/, and a(m,n) is a functional inverse of Ackermann's function. This algorithm eliminates the inherent sequentiality of the algorithm due to Malik et al. We also obtain a set of parallel algorithms running in O(log n) time using m processors and O(m) space on the CRCW PRAM, in O(log n) time using mn/logn CREW processors and O(m + n log m) space, and in O(log n) time using mn/log n EREW processors and O(mn) space, respectively. These are the first nc algorithms for solving this problem on the PRAM.
We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(I...
详细信息
We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(Iog(k)n), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(Iog(k) n) space (that is, SCk). We also introduce a variation of this heuristic that turns out to be an SCk-complete problem (the original heuristic belongs to SCk+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given. (C) 2002 Elsevier Science (USA). All rights reserved.
Orthogonal interpolation algorithms are used frequently in numerically controlled (nc) machine tool systems. Orthogonal algorithms are relatively simple to develop and implement for the interpolation function in comp...
详细信息
Orthogonal interpolation algorithms are used frequently in numerically controlled (nc) machine tool systems. Orthogonal algorithms are relatively simple to develop and implement for the interpolation function in comparison to nonorthogonal algorithms because a single coordinate axis contains each tool step. However, with nonorthogonal interpolation, feedrates and curve smoothness can be improved. In the present paper, a nonorthogonal interpolation algorithm is introduced. This algorithm can be implemented for plane curves having an f(x,y)=0 form. With the algorithm, a 28% increase in feedrate in contouring moves can be achieved without requiring any other control changes. In addition, the algorithm should be useful for some non-machining applications with even greater feedrate improvement.
We present an efficient NG algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)(2)(log n)(2)) time using O(k(n + m')) processors on an ARBITRARY...
详细信息
We present an efficient NG algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)(2)(log n)(2)) time using O(k(n + m')) processors on an ARBITRARY CRCW PRAM, where n. and m' stand for the numbers of vertices in G and edges in the simplified graph of G, respectively. (C) 2001 Academic Press.
We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O (log(2) n) time with O (n(3)) processors on a CREW PRAM,...
详细信息
We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O (log(2) n) time with O (n(3)) processors on a CREW PRAM, where n is the number of vertices of the input graph. This is the first nc algorithm for solving the problem.
The HHD-free graphs are a class of perfect graphs that strictly contain the cographs, the chordal graphs, the Matula-perfect graphs, and the Welsh-Powell opposition graphs. In this paper we present two characterizatio...
详细信息
The HHD-free graphs are a class of perfect graphs that strictly contain the cographs, the chordal graphs, the Matula-perfect graphs, and the Welsh-Powell opposition graphs. In this paper we present two characterizations of the HHD-free graphs and show how to use them to produce a parallel recognition algorithm which runs inO(logn) time usingO(n4) processors on a concurrent-read, concurrent-write parallel random access machine.
The Welsh-Powell opposition graphs have been shown to be graphs for which a certain greedy heuristic results in an optimum colouring. We propose a new characterization for this class of graphs and exploit this result ...
详细信息
The Welsh-Powell opposition graphs have been shown to be graphs for which a certain greedy heuristic results in an optimum colouring. We propose a new characterization for this class of graphs and exploit this result for the purpose of obtaining an efficient nc recognition algorithm.
We present an alternative implementation of the (1 - epsilon) factor nc approximation algorithm for the maximum weight matching by Hougardy et al. [1]. Our implementation, on the EREW PRAM model of computation, achiev...
详细信息
We present an alternative implementation of the (1 - epsilon) factor nc approximation algorithm for the maximum weight matching by Hougardy et al. [1]. Our implementation, on the EREW PRAM model of computation, achieves an O(log n) factor improvement on both the execution time and the number of processors.
Let G(V, E) be a weighted, undirected, connected simple graph with n vertices and m edges. The k most vital edge problem with respect to a minimum spanning tree is to find a set S(subset of or equal to E) of k edges i...
详细信息
Let G(V, E) be a weighted, undirected, connected simple graph with n vertices and m edges. The k most vital edge problem with respect to a minimum spanning tree is to find a set S(subset of or equal to E) of k edges in G whose removal results in the greatest increase in the weight of the minimum spanning tree in the remaining graph G(V, E - S). Although for arbitrary k, Frederickson et al. have shown that this problem is NP-hard, it is polynomial time solvable when k is fixed. In this paper we introduce a sparse, weighted k-edge connected certificate of a graph which has been found very useful, By using this certificate, we first present a general algorithm for the problem above, Then, for a fixed k > 1, we present efficient sequential and parallel algorithms. Our sequential algorithm runs in time O(n(k + 1)). Our parallel algorithm runs in time O(log n loglog n) using O(n(k + 1)) processors on an EREW PRAM. If the minimum spanning tree of G and the sparse, weighted (k + 1)-edge connected certificate of G are given, the algorithm runs in time O(log n) using O(n(k + 1)) processors on the same model. Particularly, when k = 1, we develop parallel algorithms which require O(log n loglog n) time using O(m + n(2)/(log n loglog n)) processors on an EREW PRAM, and O(log n loglog n) time using O(m) processors on a CREW PRAM respectively, and the algorithm on the EREW PRAM is the fastest, compared with previous known algorithms. (C) 1997 Elsevier science B.V.
暂无评论