Let G = (V, E) be an undirected graph with m edges and n vertices such that each edge e has a real valued weight w(e). Let MST(G) be a minimum spanning tree in G. Let f(G) be the weight of a minimum spanning tree of G...
详细信息
Let G = (V, E) be an undirected graph with m edges and n vertices such that each edge e has a real valued weight w(e). Let MST(G) be a minimum spanning tree in G. Let f(G) be the weight of a minimum spanning tree of G if G is connected;otherwise f(G) = infinity. We define a most vital edge with respect to a minimum spanning tree in a connected undirected graph G as an edge e such that f(G - e) greater-than-or-equal-to f(G - e') for every edge e' in G. In this paper, we give O(m + n log n) and O(ma(m, n)) time algorithms, which improve O(m log m) and O(n2) time bounds by Hsu et al. in Inform. Process. Lett. 39 (1991) 277-281.
We present a new linear algorithm for coloring the edges of a tree. Although this is not the first linear algorithm for the problem, our algorithm unlike the existing ones can be parallelized directly. The paralleliza...
详细信息
We present a new linear algorithm for coloring the edges of a tree. Although this is not the first linear algorithm for the problem, our algorithm unlike the existing ones can be parallelized directly. The parallelization is obtained by showing that edge-coloring can be carried out using tree contraction. Hence, it can be done in O(log n) time using n/log n processors on the EREW PRAM. When the problem is extended to one of coloring the edges of a graph with edge-disjoint cycles, the said algorithm for trees can be extended very easily without increasing the resource requirement.
Multiple sequence alignment is an important problem in computational molecular biology. Dynamic programming for optimal multiple alignment requires too much time to be practical. Although many algorithms for suboptima...
详细信息
Multiple sequence alignment is an important problem in computational molecular biology. Dynamic programming for optimal multiple alignment requires too much time to be practical. Although many algorithms for suboptimal alignment have been suggested, no "performance guarantees" algorithms have been known until recently. A computationally efficient approximation multiple alignment algorithm with guaranteed error bounds equal to the normalized communication cost of a corresponding graph is given in this paper. Recently, Altschul and Lipman [SIAM J. Appl. Math., 49 (1989), pp. 197-2091 used suboptimal alignments for reducing the computational complexity of the optimal alignment algorithm. This paper develops the Altschul-Lipman approach and demonstrates that bounds for optimal multiple alignment of k sequences can be derived from a solution of the maximum weighted matching problem in a k-vertex graph. Fast maximum matching algorithms allow efficient implementation of dynamic bounds for the multiple alignment problem.
In this paper we study subtree isomorphism and its relationships with some important symbolic problems. Recently, a linear time algorithm for ordered subtree isomorphism was given by Makinen. We note that a subtree of...
详细信息
In this paper we study subtree isomorphism and its relationships with some important symbolic problems. Recently, a linear time algorithm for ordered subtree isomorphism was given by Makinen. We note that a subtree of a rooted tree T, in Makinen's paper, refers to the tree rooted at any vertex in T. We consider ordered subtree isomorphism when a broader definition of subtree is used, viz., a subtree of T is any connected subgraph, including upsilon, of the tree rooted at any vertex-upsilon in T. We give some evidence to show that a linear time algorithm for this problem is unlikely. We also give an almost linear time reduction from the important problem of pattern matching to ordered subtree isomorphism. Finally, we present simpler linear time algorithms for ordered and unordered subtree isomorphism (with the more restrictive definition of subtree).
A complete characterization of the class of graphs that admit a cylindric visibility representation is presented, where vertices are represented by intervals parallel to the axis of the cylinder and the edges correspo...
详细信息
A complete characterization of the class of graphs that admit a cylindric visibility representation is presented, where vertices are represented by intervals parallel to the axis of the cylinder and the edges correspond to pairs of visible intervals. Moreover, linear time algorithms are given for testing the existence of and constructing such a representation. Important applications of cylindric visibility representations can be found in the layout of regular VLSI circuits, such as linear systolic arrays and bit-slice architectures. Also, alternative "dual" characterizations are presented of the graphs that admit visibility representations in the plane and in the cylinder. It is interesting to observe that neither of these two classes is contained in the other, although they have a nonempty intersection.
This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of a...
详细信息
This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn ≥m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherer≤mn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenr～n, but it degrades to Θ(mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered ≤r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.
Two parallel algorithms for finding the lowest common ancestors of a set of vertex pairs Q (the query set) in a directed tree are presented. With all the overheads taken into account, these algorithms take O((n + QI) ...
详细信息
Two parallel algorithms for finding the lowest common ancestors of a set of vertex pairs Q (the query set) in a directed tree are presented. With all the overheads taken into account, these algorithms take O((n + QI) P log2 n) and O(n2/p + log2n) time, respectively, with p(> 0) processors (n is the size of the tree). These results are better than the best known result in that the first achieves the O(log2 n) time bound with only n + |Q| processors while the second reduces the number of processors used by a factor of log2 n which is optimal for large query sets when 0 < p ≤ n2/log2 n. The computer model we use here is the PRAM which is an SIMD model allowing read but not write conflicts. Our results also imply the following improvements: the processor bound for finding a set of fundamental cycles in an undirected graph is improved by a factor of log2 n and the result is optimal for dense graphs; the implementations of some other sequential and parallel algorithms are also simplified.
algorithms synthesis is a new approach in the field of design and analysis of algorithms. Darlington (1978) presented a tree structure starting from a high level definition (by defining permutation function) as root-...
详细信息
algorithms synthesis is a new approach in the field of design and analysis of algorithms. Darlington (1978) presented a tree structure starting from a high level definition (by defining permutation function) as root-node and finally obtaining 6 terminal-nodes corresponding to each sorting algorithm he discussed. The algorithms-synthesis approach starts from a high level definition and ultimately results in the required algorithms. An attempt is made to synthesize some scheduling algorithms starting, as Darlington did, from a high level definition, and using program transformation techniques. Three scheduling algorithms are taken into the synthesis: 1. First-Come-First-Serve, 2. Round-Robin, and 3. Selfish-Round-Robin. The rules applied are mainly the unfolding-and-folding technique as examined by Burstall and Darlington (1977).
暂无评论