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

14th Prague Stringology Conference (PSC)

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Scuola Super Catania I-95123 Catania Italy

ISBN: (纸本)9788001044032

The Pattern Matching problern with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks to compute, for every text location with a swapped match of P the number of swaps necessary to obtain a match at the location. in this paper, we present new efficient algorithms for the Approximatc, Swap Matching problem. In particular, we first present a O(nm(2)) algorithm, where fn is the length of the pattern and n is the length of the text, which is a variation of the BACKWARD-CROSSSAMPLING algorithm, a recent solution to the swap matching problem. Subsequently, we propose an efficient implementation of our algorithm, based on the bit-parallelism technique. The latter solution achieves a O(mn)-time and O(sigma)-space complexity, where a is the dimension of the alphabet. From an extensive comparison with some of the most recent and effective algorithms for the approximate swap matching problem, it turns out that our algorithms are very flexible and achieve very good results in practice.

关键词： approximate pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Pattern Matching with Swaps for Short Patterns in Linear Time

Pattern Matching with Swaps for Short Patterns in Linear Tim...

引用

35th Conference on Current Trends in Theory and Practice of Computer Science

作者： Cantone, Domenico Faro, Sinione Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

ISBN: (纸本)9783540958901

The Pattern Matching problem with Swaps consists in finding all occurrences of a, pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper, we present a new approach for solving both the Swap Matching problem and the Approximate Swap Matching problem in linear time, in the case of short, patterns. In particular, we devise a O(nm) general algorithm, named CROSS-SAMPLINGING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(n) worst-case time and O(sigma)-space complexity, with patterns whose length is comparable to the word-size of the target machine.

关键词： pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A New Algorithm for Efficient Pattern Matching with Swaps

A New Algorithm for Efficient Pattern Matching with Swaps

引用

20th International Workshop on Combinatorial algorithms (IWOCA)

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Univ Catania Scuola Super Catania Via San Nullo 5-I I-95123 Catania Italy Univ Catania Dipt Matemat Informat I-95124 Catania Italy

ISBN: (纸本)9783642102165

The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text;T, when disjoint local swaps in the pattern are allowed. In this paper, we present a new efficient algorithm for the Swap Matching problem with short patterns. In particular, we devise a O(nm(2)) general algorithm, named BACKWARD-CROSS-SAMPLING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(nm) worst-case time and O(sigma)-space complexity, with patterns whose length m is comparable to the word-size of the target machine (n and sigma are respectively the size of the text and of the alphabet). From an extensive comparison with some of the most recent and effective algorithms for the swap matching problem, it turns out that our algorithm is very flexible and achieves very good results in practice.

关键词： pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A Time-Randomness Tradeoff for Quasi-Random Rumour Spreading

引用

Electronic Notes in Discrete Mathematics 2009年 34卷 335-339页

作者： Doerr, Benjamin Fouz, Mahmoud Max-Planck-Institut für Informatik D-66123 Saarbrücken Germany Universität des Saarlandes D-66123 Saarbrücken Germany

We give a time-randomness tradeoff for the quasi-random rumour spreading protocol proposed by Doerr et al [Doerr, B., T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proc. of the 19th Annual ACM-SIAM Symp. on Disc. Alg., pages 773-781, 2008] on complete graphs. In this protocol, the goal is to spread a piece of information originating from one vertex throughout the network. Each vertex is assumed to have a (cyclic) list of its neighbors. Once a vertex is informed by one of its neighbors, it chooses a position in its list uniformly at random and goes on to inform its neighbors starting from that position and proceeding in order of the list. Doerr et al [Doerr, B., T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proc. of the 19th Annual ACM-SIAM Symp. on Disc. Alg., pages 773-781, 2008.] showed that after O(log n) rounds, the rumour will have been broadcasted to all nodes with probability 1 - o (1). We study the broadcast time when the amount of randomness available at each node is reduced. For randomness parameter ℓ, we show that there exists lists such that (1 - ε) (log₂ n + ln n - log₂ ℓ - ln ℓ) + ℓ steps are needed to inform every vertex with probability at least 1 - O (e^{- frac(nε, 2 ln n)}). © 2009 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms Randomness in Computation

来源：评论

学校读者我要写书评

暂无评论

ASK NOT WHAT STRINGOLOGY CAN DO FOR YOU: ADVANCES IN PATTERN MATCHING DRIVEN BY COMPUTATIONAL BIOLOGY

引用

COMMUNICATIONS IN INFORMATION AND SYSTEMS 2009年第3期9卷 235-252页

作者： Apostolico, Alberto Univ Padua Padua Italy Georgia Inst Technol Atlanta GA 30332 USA Univ Padua Dipartimento Ingn Informaz Padua Italy Georgia Inst Technol Coll Comp Atlanta GA 30318 USA

Molecular biology has posed a number of fascinating and sometimes daunting computational problems, which came naturally expressed in its native language of character strings. Through the years, some such problems have found elegant and even useful solutions in response to the needs that originally motivated them. What is perhaps even more remarkable, several of the ideas inspired by computational molecular biology have found application in remote and diverse domains, so that it may be argued that molecular biology did more for computing than the latter did for it. As a modest tribute, this paper reviews a small sample of these cases drawing from the personal exposure of the author.

关键词： Computational biology design and analysis of algorithms Pattern matching Pattern discovery Motif Sequence alignment Waka Freakanomics Data analysis Data compression

来源：评论

学校读者我要写书评

暂无评论

On the algorithmic aspects of discrete and lexicographic Helly-type theorems and the discrete LP-type model

引用

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 1-45页

作者： Halman, Nir MIT Dept Civil & Environm Engn Cambridge MA 02139 USA

Helly's theorem says that, if every d+1 elements of a given finite set of convex objects in R-d have a common point, there is a point common to all of the objects in the set. In discrete Helly theorems the common point should belong to an a priori given set. In lexicographic Helly theorems the common point should not be lexicographically greater than a given point. Using discrete and lexicographic Helly theorems we get linear time solutions for various optimization problems. For this, we introduce the DLP-type (discrete linear programming-type) model, and provide new algorithms that solve in randomized linear time fixed-dimensional DLP-type problems. For variable-dimensional DLP-type problems, our algorithms run in time subexponential in the combinatorial dimension. Finally, we use our results in order to solve in randomized linear time problems such as the discrete p-center on the real line, the discrete weighted 1-center problem in R-d with either l(1) or l(infinity) norm, the standard (continuous) problem of finding a line transversal for a totally separable set of planar convex objects, a discrete version of the problem of finding a line transversal for a set of axis-parallel planar rectangles, and the (planar) lexicographic rectilinear p-center problem for p = 1, 2, 3. These are the first known linear time algorithms for these problems. Moreover, we use our algorithms to solve in randomized subexponential time various problems in game theory, improving upon the best known algorithms for these problems.

关键词： Helly-type theorems LP-type model design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Motif patterns in 2D

引用

THEORETICAL COMPUTER SCIENCE 2008年第1期390卷 40-55页

作者： Apostolico, Alberto Parida, Laxmi Rombo, Simona E. Univ Calabria DEIS I-87036 Arcavacata Di Rende Italy Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Univ Padua Dept Informat Engn I-35131 Padua Italy IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Motif patterns consisting of sequences of intermixed solid and don't-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms. (C) 2007 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms pattern matching pattern discovery motif 2D irredundant motifs

来源：评论

学校读者我要写书评

暂无评论

Incremental discovery of the irredundant motif bases for all suffixes of a string in O(n² log n) time

引用

THEORETICAL COMPUTER SCIENCE 2008年第2-3期408卷 106-115页

作者： Apostolico, Alberto Tagliacollo, Claudia Accademia Nazl Lincei Rome Italy Georgia Inst Technol Coll Comp Atlanta GA 30318 USA

Compact bases formed by motifs called "irredundant" and capable of generating all other motifs in a sequence have been proposed in recent years and successfully tested in tasks of biosequence analysis and classification. Given a sequence s of n characters drawn from an alphabet Sigma, the problem of extracting such a base from s had been previously solved in time O(n(2) log n log vertical bar Sigma vertical bar) and O(vertical bar Sigma vertical bar n(2) log(2) n log log n), respectively, using the FFT-based string searching by Fischer and Paterson. More recently, a solution on binary strings taking time O(n(2)) without resorting to the FFT was also proposed. In the present paper, we considered the problem of incrementally extracting the bases of all suffixes of a string. This problem was solved in a previous work in time O(n(3)). A much faster incremental algorithm is described here, which takes time O(n(2) log n) for binary strings. Although this algorithm does not make use of the FFT, its performance is comparable to the one exhibited by the previous FFT-based algorithms involving the computation of only one base. The implicit representation of a single base requires O(n) space, whence for finite alphabets the proposed solution is within a log n factor from optimality. (C) 2008 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms Pattern matching Motif discovery Irredundant motif Base

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms and complexity results for power domination in graphs

引用

ALGORITHMICA 2008年第2期52卷 177-202页

作者： Guo, Jiong Niedermeier, Rolf Raible, Daniel Univ Jena Inst Informat D-07743 Jena Germany Univ Trier Abt Informat Wirtschaftsinformat Fachbereich 4 D-54286 Trier Germany

The NP-complete POWER DOMINATING SET problem is an "electric power networks variant" of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum-size set P. V such that all vertices in V are "observed" by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that POWER DOMINATING SET can be solved by "bounded-treewidth dynamic programs." For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for POWER DOMINATING SET in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that POWER DOMINATING SET remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that POWER DOMINATING SET parameterized by vertical bar P vertical bar is W[2]-hard and it cannot be better approximated than DOMINATING SET.

关键词： design and analysis of algorithms computational complexity parameterized complexity fixed-parameter algorithms graph algorithms graphs of bounded treewidth (power) domination in graphs

来源：评论

学校读者我要写书评

暂无评论

Finding a maximum-density path in a tree under the weight and length constraints

引用

INFORMATION PROCESSING LETTERS 2008年第5期105卷 202-205页

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

Let T = (V, E) be a tree with n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where the value val(v) is a real number and the weight w(v) is a positive integer. The density of a path P = (v(1), v(2).....v(k)) is defined as Sigma(k)(i=1) val(i)/Sigma(k)(i=1)w(i). The weight of P, denoted by w(P), is Sigma(k)(i=1)w(i). Given a tree of n nodes, two integers w(min) and w(max), and a length lower bound L, we present a pseudo-polynomial O(w(max)nL)-time algorithm to find a maximum-density path P in T such that W-min <= w(P) <= w(max) and the length of P is at least L. (c) 2007 Elsevier B.V. All rights reserved.

关键词： algorithms design and analysis of algorithms trees paths subgraph optimization problems network design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：