检索结果-内蒙古大学图书馆

An efficient algorithm to generate all maximal independent sets on trapezoid graphs

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1999年第4期70卷 587-599页

作者： Hota, M Pal, M Pal, TK Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India Midnapore Coll Dept Math Midnapore 721101 India

Generation of all maximal independent sets (MIS) is a NP-complete problem for general graphs. In this paper, using a particular geometric property of trapezoid graph, an efficient algorithm is designed which enables to generate an maximal independent sets for a trapezoid graph in O(n (m) over bar + alpha n) time, where (m) over bar and alpha are respectively the number of edges of the complement graph of the given graph and the number of generated maximal independent sets. There is no prior algorithm available to solve this problem of finding all MIS for trapezoid graphs.

关键词： design and analysis of algorithms data structure independent sets trapezoid graph tree

来源：评论

学校读者我要写书评

暂无评论

FINDING LOWEST COMMON ANCESTORS IN PARALLEL

引用

IEEE TRANSACTIONS ON COMPUTERS 1986年第8期35卷 764-769页

作者： TSIN, YH MEM UNIV NEWFOUNDLAND DEPT COMP SCIST JOHNS A1C 5S7NEWFOUNDLANDCANADA

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.

关键词： design and analysis of algorithms PRAM SIMD models fundamental cycles lowest common ancestors parallel computation parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

MULTIPLE ALIGNMENT, COMMUNICATION COST, AND GRAPH MATCHING

引用

SIAM JOURNAL ON APPLIED MATHEMATICS 1992年第6期52卷 1763-1779页

作者： PEVZNER, PA Univ of Southern California Los Angeles CA USA

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.

关键词： SEQUENCE ALIGNMENT BIOLOGICAL SEQUENCES design and analysis of algorithms APPROXIMATION algorithms DYNAMIC PROGRAMMING MAXIMUM MATCHING

来源：评论

学校读者我要写书评

暂无评论

On minimum-area hulls

引用

ALGORITHMICA 1998年第1期21卷 119-136页

作者： Arkin, EM Chiang, YJ Held, M Mitchell, JSB Sacristan, V Skiena, SS Yang, TC SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA Salzburg Univ Inst Comp Wissensch A-5020 Salzburg Austria Univ Politecn Catalunya Dept Matemat Applicada 2 E-08028 Barcelona Spain SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Kyungsung Univ Dept Comp Sci & Stat Nam Gu Pusan 608736 South Korea

We study some minimum-area hull problems that generalize the notion of convex hull to starshaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n-vertex simple polygon P, find a minimum-area, star-shaped polygon P* containing P. This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P* are constrained to be vertices of P, and the unrestricted version, in which the vertices of P* can be anywhere in the plane. We prove that the restricted problem falls in the class of "3SUM-hard" (sometimes called "n(2)-hard") problems, which are suspected to admit no solutions in o(n(2)) time. Further, we give an O(n(2)) time algorithm, improving the previous bound of O(n(5)). We also show that the unrestricted problem can be solved in O(n(2)p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O (n). We also consider the case in which P* is required to be monotone, with respect to an unspecified direction;we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of O (n log n) time for computing P* in the restricted version, and an upper bound of O (nq(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n).

关键词： minimum-area hulls star-shaped polygons monotone polygons 3SUM-hardness lower bounds computational geometry design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Motif discovery by monotone scores

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 695-706页

作者： Apostolico, Alberto Pizzi, Cinzia Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

The detection of frequent patterns such as motifs and higher aggregates is of pat-amount interest in biology and invests many other applications of automated discovery. The problem with its variants is usually plagued with computational burden. A related difficulty is posed by the fact, that due to the sheer mole of candidates, the tables and indices at the outset tend to be bulky, unmanageable, and ultimately uninformative. For solid patterns, it is possible to compact the size of statistical indices by resort to certain monotonicities exhibited by popular scores. The savings come from the fact that these monotonicities enable one to partition the candidate over-represented words into families in such a way that it suffices to consider and weigh only one candidate per family. In this paper, we study the problem of extracting, from given source x and error threshold k, substrings of x that occur unusually often in x within k substitutions or mismatches. Specifically, we assume that the input textstring x of n characters is produced by an i.i.d. source. and design efficient methods for computing the probability and expected number of occurrences for substrings of x with (either exactly or up to) k mismatches. Two related schemes are presented. In the first one, an O(nk) time preprocessing of x is developed that supports the following subsequent query: for any substring w of x arbitrarily specified as input, the probability of occurrence of w in x within (either exactly or up to) k mismatches is reported in O(k(2)) time. In the second scheme, a length or length range is arbitrarily specified, and the above probabilities are computed for all substrings of x having length in that range, in overall O(nk) time. Further, monotonicity conditions are introduced and studied for the probability and expected frequency of a substring under extension, increased number of errors, or both. Over intervals of constant frequency count, these monotonicities translate to some of the sco

关键词： design and analysis of algorithms pattern matching pattern discovery motif over-represented word monotone score correction factor

来源：评论

学校读者我要写书评

暂无评论

Approximating Spanning Trees with Few Branches

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 181-196页

作者： Chimani, Markus Spoerhase, Joachim Univ Jena Inst Comp Sci Jena Germany Univ Wurzburg Inst Comp Sci D-97070 Wurzburg Germany

Given an undirected, connected graph, the aim of the minimum branch-node spanning tree problem is to find a spanning tree with the minimum number of nodes of degree larger than 2. The problem is motivated by network design problems where junctions are significantly more expensive than simple end- or through-nodes, and are thus to be avoided. Unfortunately, it is NP-hard to recognize instances that admit an objective value of zero, rendering the search for guaranteed approximation ratios futile. We suggest to investigate a complementary formulation, called maximum path-node spanning tree, where the goal is to find a spanning tree that maximizes the number of nodes with degree at most two. While the optimal solutions (and the practical applications) of both formulations coincide, our formulation proves more suitable for approximation. In fact, it admits a trivial 1/2-approximation algorithm. Our main contribution is a local search algorithm that guarantees a ratio of 6/11, as well as showing that the problem is APX-hard, i.e., it does not allow a PTAS.

关键词： Theory of computation design and analysis of algorithms Approximation algorithms analysis Routing and network design problems

来源：评论

学校读者我要写书评

暂无评论

On the common substring alignment problem

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2001年第2期41卷 338-359页

作者： Landau, GM Ziv-Ukelson, M Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Polytech Univ Six MetroTech Ctr Dept Comp & Informat Sci Brooklyn NY 11201 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S-1, S-2. . . S-c and a target string T, Y is a common substring of all strings S-i that is, S-i = BiYFi. The goal is to compute the similarity of all strings S-i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Yin a source string would require the computation of all the values in a dynamic programming table of size O(nl) where l is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage:, a data structure is constructed which encodes the: comparison of Y with T. Then, during the alignment stage, for each comparison of a source S-i with T, the precompiled data structure is used to speed up the part of Y. We show how to reduce the O(nl) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nl) encoding work, which is executed only once. (C) 2001 Elsevier Science.

关键词： design and analysis of algorithms dynamic programming sequence comparison repeated substrings shared substrings Monge arrays candidate lists

来源：评论

学校读者我要写书评

暂无评论

Faster two-dimensional pattern matching with rotations

引用

THEORETICAL COMPUTER SCIENCE 2006年第3期368卷 196-204页

作者： Amir, Amihood Kapah, Oren Tsur, Dekel Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n(2)m(3)), where the size of the text is n x n and the size of the pattern is m x m. In this paper we present a new algorithm for the problem whose running time is 0(n(2),m(2)). (c) 2006 Published by Elsevier B.V.

关键词： design and analysis of algorithms two-dimensional pattern matching rotation

来源：评论

学校读者我要写书评

暂无评论

The internal Steiner tree problem: Hardness and approximations

引用

JOURNAL OF COMPLEXITY 2013年第1期29卷 27-43页

作者： Huang, Chao-Wen Lee, Chia-Wei Gao, Huang-Ming Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Given a graph G = (V, E) with a cost function c : E -> R+ and a vertex subset R subset of V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost Sigma((u,v)is an element of E(T)) c(u, v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2 rho + 1)-approximation algorithm for solving the problem on complete graphs, where rho is an approximation ratio for the Steiner tree problem. Currently, the best-known rho is In 4+is an element of < 1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 9/7-approximation algorithm for the problem. (c) 2012 Elsevier Inc. All rights reserved.

关键词： VLSI routing Approximation algorithms MAX SNP-hardness Steiner trees The internal Steiner tree problem design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

An effcient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第2期193卷 408-418页

作者： Hsieh, Sun-Yuan Huang, Chao-Wen Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 70101 Taiwan

Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we efficiently solve two subtree-comparison problems on a set of phylogenetic trees which have practical applications to analyze the evolution and co-evolution genes clustering of genomic sequences. Let T-1, T-2, ..., T-k be a set of k phylogenetic trees such that the leaves of each tree are drawn from {1, 2, ..., n} and the leaves for two arbitrary trees are not necessary the same, where n is the maximum number of the leaves among the k trees. We present a linear-time algorithm to find all the leaf-agreement descendant subtrees. By further extending this result, we present a linear-time algorithm to find all the leaf-agreement isomorphic descendant subtrees. Based on our algorithms, a web-based system using input tree files from TreeBASE is also implemented. (C) 2007 Elsevier Inc. All rights reserved.

关键词： knowledge discovery tree pattern retrieval phylogenetic trees descendant subtrees web-based system TreeBASE design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：