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

An optimal parallel algorithm to construct a tree 3-spanner on interval graphs

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2005年第3期82卷 259-274页

作者： Saha, A Pal, M Pal, TK Vidasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 W Bengal India

A spanning tree T is said to be a tree t-spanner of a graph G if the distance between any two vertices in T is at most t times their distance in G. The tree t-spanner has many applications in network and distributed environments. This problem is NP-hard for general graph even for some special classes of graphs. This problem is polynomial solvable for interval graph when t greater than or equal to 3. When t = 2 the exact complexity of the problem still remains open, but, for t = 2 a polynomial time 2-approximation algorithm is available. An O(n + in) time sequential algorithm is available to solve tree 3-spanner problem. where In and n, respectively, represent the number of edges and the number of vertices of the interval graph. Here, a parallel algorithm is designed to solve a tree 3-spanner problem in O(log n) time using O(n/log n) processors on an EREW PRAM. As a byproduct, a parallel algorithm is also designed to find the increasing sequence of numbers of a set of N numbers in O(log N) time using O(N/log N) processors.

关键词： parallel algorithms design and analysis of algorithms t-spanner tree t-spanner interval graph

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT PRAM ALGORITHM FOR MAXIMUM-WEIGHT INDEPENDENT SET ON PERMUTATION GRAPHS

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2005年第1-2期19卷 77-92页

作者： Saha, Anita Pal, Madhumangal Pal, Tapan K. Vidyasagar Univ Midnapore W Bengal India Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 W Bengal India Kharagpur Coll Kharagpur W Bengal India

An efficient parallel algorithm is presented to find a maximum weight independent set of a permutation graph which takes O(log n) time using O(n(2)/log n) processors on an EREW PRAM, provided the graph has at most O(n) maximal independent sets. The best known parallel algorithm takes O(log(2) n) time and O(n(3)/log n) processors on a CREW PRAM.

关键词： design and analysis of algorithms parallel algorithms independent set permutation graph

来源：评论

学校读者我要写书评

暂无评论

Optimal discovery of repetitions in 2D

引用

DISCRETE APPLIED MATHEMATICS 2005年第1-3期151卷 5-20页

作者： Apostolico, A Brimkov, VE Univ Padua Dipartimento Ingn Informat I-35131 Padua Italy Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA

Repetitive substructures in two-dimensional arrays emerge in speeding up searches and have been recently studied also independently in an attempt to parallel some of the classical derivations concerning repetitions in strings. The present paper focuses on repetitions in two dimensions that manifest themselves in form of two "tandem" occurrences of a same primitive rectangular pattern W where the two replicas touch each other with either one side or corner. Being primitive here means that W cannot be expressed in turn by repeated tiling of another array. The main result of the paper is an O(n(3) log n) algorithm for detecting all "side-sharing" repetitions in an n x n array. This is optimal, based on bounds on the number of such repetitions established in previous work. With easy adaptations, these constructions lead to an equally optimal, O(n(4)) algorithm for repetitions of the second type. (c) 2005 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms pattern matching pattern discovery 2D arrays tandem repetition

来源：评论

学校读者我要写书评

暂无评论

Optimal discovery of repetitions in 2D

Optimal discovery of repetitions in 2D

引用

9th International Workshop on Combinatorial Image analysis

作者： Apostolico, A Brimkov, VE Univ Padua Dipartimento Ingn Informat I-35131 Padua Italy Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA

关键词： design and analysis of algorithms pattern matching pattern discovery 2D arrays tandem repetition

来源：评论

学校读者我要写书评

暂无评论

Extracting approximate patterns

引用

JOURNAL OF DISCRETE algorithms 2005年第2-4期3卷 293-320页

作者： Pelfrene, Johann Abdeddaim, Said Alexandre, Joel ExonHit Therapeut 65 Blvd Massena F-75103 Paris France Univ Rouen ABISS UMR 6037 F-76821 Mont St Aignan France Univ Rouen ABISS LIFAR F-76821 Mont St Aignan France

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis. We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q - 1 times, in time O(|Sigma| Nn(2) log n), where Sigma is the alphabet. In the particular case where q = 2, the complexity in time is only O(|Sigma| n(2) log n). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential. (C) 2004 Elsevier B. V. All rights reserved.

关键词： design and analysis of algorithms String matching Pattern discovery Don't care character Primitive pattern

来源：评论

学校读者我要写书评

暂无评论

Two-dimensional pattern matching with rotations

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-2期314卷 173-187页

作者： Amir, A Butman, A Crochemore, M Landau, GM Schaps, M Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Univ Marne La Vallee Inst Gaspard Monge London England Kings Coll London London WC2R 2LS England Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Polytech Univ Dept Comp & Informat Sci MetroTech Ctr 6 Brooklyn NY 11201 USA Bar Ilan Univ Dept Math IL-52900 Ramat Gan Israel

The problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. We prove an upper and lower bound on the number of such different possible rotated patterns. Subsequently, given an m x m array (pattern) and an n x n array (text) over some finite alphabet Sigma, we present a new method yielding an O(n(2)m(3)) time algorithm for this problem. (C) 2003 Published by Elsevier B.V.

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

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for string matching with k mismatches

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2004年第2期50卷 257-275页

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length in and every length in substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil-Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O (nk). The Abrahamson algorithm finds the number of mismatches at every location in time O (nrootm log m). We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time O(nrootk log k). We also show an algorithm that solves the above problem in time O ((n + (nk(3))/m) log k). (C) 2003 Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

On the algorithm of Berztiss for tree pattern matching

On the algorithm of Berztiss for tree pattern matching

引用

5th Mexican International Conference in Computer Science (ENC 2004)

作者： Valiente, G Tech Univ Catalonia Dept Software E-08034 Barcelona Spain

ISBN: (纸本)0769521606

The tree pattern matching problem over labeled trees is addressed in this paper Several tree pattern matching algorithms are known which are based on the decomposition of the pattern into strings, with each string representing a root-to-leaf path. Among these, Alfs T. Berztiss gave a simple tree pattern matching algorithm which remained unknown to the research community. In this paper the tree pattern matching algorithm of Berztiss is reviewed, its correctness is established, and its complexity is shown to be O(mn) time and space in the worst case and O(n) on the average, where n is the text size and m is the pattern size.

关键词： design and analysis of algorithms combinatorial problems tree pattern matching subtree isomorphism

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for string matching with k mismatches

Faster algorithms for string matching with <i>k</i> mismatch...

引用

11th Annual ACM/SIAM Symposium on Discrete algorithms

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

ISBN: (纸本)0898714532

关键词： design and analysis of algorithms combinatorial algorithms on words approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Overlap matching

引用

INFORMATION AND COMPUTATION 2003年第1期181卷 57-74页

作者： Amir, A Cole, R Hariharan, R Lewenstein, M Porat, E IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Georgia Tech Coll Comp Atlanta GA 30332 USA NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA Indian Inst Sci CSA Dept Bangalore 560012 Karnataka India

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A "match" is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(n log m), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). Our reduction provides a solution to the pattern matching with swaps problem in time 0 (n log m log a). (C) 2002 Elsevier Science (USA). All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：