Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. ...
详细信息
Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations, in graphs, we obtain a (3 beta/4 + 3 beta(2)/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an insfance of beta-TSP, if it is a complete graph with edge weights c: E(G) -> Q >= 0 that are restricted as follows. For each triple of vertices u, v, w is an element of V (G), c({u, v}) <= beta(c({u, w}) + c ({w, v})). (C) 2015 Elsevier B.V. All rights reserved.
The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or ...
详细信息
The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or consider only two sequences. Recently, with the rise of whole-genome duplication research, the doubly conserved synteny relationship among three sequences should be considered. It is a brand new model to find a merging way for understanding the interleaving relationship of sequences. Here, we define the merged LCS problem for measuring the interleaving relationship among three sequences. An 0(113) algorithm is first proposed for solving the problem, where it is the sequence length. We further discuss the variant version of this problem with the block information. For the blocked merged LCS problem, we propose an algorithm with time complexity O(n(2)m), where in is the number of blocks. An improved O(n(2)+nm(2)) algorithm is further proposed for the same blocked problem. (c) 2007 Published by Elsevier B.V.
We present a new transitive closure algorithm that is based on strong component detection. The new algorithm is more efficient than the previous transitive closure algorithms that are based on strong components detect...
详细信息
We present a new transitive closure algorithm that is based on strong component detection. The new algorithm is more efficient than the previous transitive closure algorithms that are based on strong components detection, since it does not generate unnecessary partial successor sets and scans the input graph only once.
We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algo...
详细信息
We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(log n) time and O(m + n) work. The algorithm is a parallelization of King's Linear time sequential algorithm for the problem. (C) 1997 Elsevier Science B.V.
This paper introduces the maximum constrained agreement subtree problem, which is a generalization of the classical maximum agreement subtree problem. This new problem is motivated by the understood constraint when we...
详细信息
This paper introduces the maximum constrained agreement subtree problem, which is a generalization of the classical maximum agreement subtree problem. This new problem is motivated by the understood constraint when we compare the evolutionary trees. We give an O(n log n)-time algorithm for solving the problem when the input trees are binary. The time complexity of our algorithm matches the fastest known algorithm for the maximum agreement subtree problem for binary trees. (c) 2006 Elsevier B.V. All rights reserved.
We introduce a pre-test for bivariate polynomial factorization over F-2, which combines the basic structure of an algorithm due to Lecerf (2010) [14] with ideas of Gao (2003) [5]. (C) 2017 Elsevier B.V. All rights res...
详细信息
We introduce a pre-test for bivariate polynomial factorization over F-2, which combines the basic structure of an algorithm due to Lecerf (2010) [14] with ideas of Gao (2003) [5]. (C) 2017 Elsevier B.V. All rights reserved.
We consider some special cases of the restricted assignment problem. In this scheduling problem on parallel machines, any job j can only be assigned to one of the machines in its given subset M-j of machines. We give ...
详细信息
We consider some special cases of the restricted assignment problem. In this scheduling problem on parallel machines, any job j can only be assigned to one of the machines in its given subset M-j of machines. We give an LP-formulation for the problem with two job sizes and show that it has an integral optimal solution. We also present a PTAS for the case that the M-j's are intervals of the same length. Further, we give a new and very simple algorithm for the case that vertical bar M-j vertical bar = 2 (known as the graph balancing problem) with ratio 11/6. (C) 2016 Elsevier B.V. All rights reserved.
Given a set of Unique Input Output (UIO) sequences for states of a Finite State Machine (FSM), the optimality of the length of a test sequence for the FSM can be determined with respect to the class of test sequences ...
详细信息
Given a set of Unique Input Output (UIO) sequences for states of a Finite State Machine (FSM), the optimality of the length of a test sequence for the FSM can be determined with respect to the class of test sequences that satisfy the same requirements for the starting and terminating states. The first class requires test sequences to begin and end at the initial state v(1);the second class requires only that test sequences begin at the initial state v(1);and the third class imposes no requirements whatsoever on the starting and terminating states. Based on this classification, lower bounds on the length of test sequences are established. For a special case, FSMs with no convergent states, polynomial-time algorithms for the construction of optimal-length test sequences achieving these lower bounds are given.
Given two strings P and T , m =| P |, n =| T |, m 0. We follow a new approach to SM k based on the determination of the permutations of P in T , and propose two algorithms for its solution. The first algorithm is very...
详细信息
Given two strings P and T , m =| P |, n =| T |, m < n , the classical problem of string matching with k mismatches (SM k ) is the one of finding all the occurrences of P in T with at most k < m mismatching symbols. The best existing algorithms require time of O( n ) for k =0, and O ( m log m + nk ) for k >0. We follow a new approach to SM k based on the determination of the permutations of P in T , and propose two algorithms for its solution. The first algorithm is very simple. It runs in time O ( n log | A P |+ rm ), where A P is the alphabet of P , and r < n is the number of occurrences in T of the permutations of P with up to k mismatches. The second algorithm, which makes use of a suffix tree, runs in time O ( n log | A P |+ dk ), where d ⩽ r is upper bounded by the number of distinct permutations of P in T with up to k mismatches. An extensive set of runs shows that rm < nk and d ⪡ n , and that the running times are strongly reduced, thus making our algorithms important in practice.
For any fixed1 k > 0, we obtain (a) an O(alpha2 log alpha log(k)n) time parallel algorithm for (alpha + 1) coloring an alpha-degree graph with n/log(k)n processors on an EREW PRAM, (b) an O(alpha2 log alpha log(k)n...
详细信息
For any fixed1 k > 0, we obtain (a) an O(alpha2 log alpha log(k)n) time parallel algorithm for (alpha + 1) coloring an alpha-degree graph with n/log(k)n processors on an EREW PRAM, (b) an O(alpha2 log alpha log(k)n) time parallel algorithm for 3-coloring an alpha-degree rooted tree with n/log(k)n processors on a CREW PRAM, (c) an O(log(k)n) time parallel algorithm for finding a Maximal Independent Set of a rooted tree on an ARBITRARY CRCW PRAM.
暂无评论