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

An optimal PRAM algorithm for a spanning tree on trapezoid graphs

Journal of Applied Mathematics and Computing 2003年第1-2期12卷 21-29页

作者： Bera, Debashis Pal, Madhumangal Pal, Tapan K. Dept. Appl. Math. Ocean. Comp. Prog. Vidyasagar University Midnapore-721 102 India

Let G be a graph with n vertices and m edges. The problem of constructing a spanning tree is to find a connected subgraph of G with n vertices and n - 1 edges. In this paper, we propose an O(log n) time parallel algor... 详细信息

关键词： design and analysis of algorithms Parallel algorithms Spanning tree Trapezoid graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient text fingerprinting via parikh mapping

引用

Journal of Discrete algorithms 2003年第5-6期1卷 409-421页

作者： Amir, Amihood Apostolico, Alberto Landau, Gad M. Satta, Giorgio Department of Mathematics and Computer Science Bar-Ilan University 52900 Ramat-Gan Israel Dipartimento di Elettronica e Informatica Università di Padova 35131 Padova Via Gradenigo 6/A Italy Department of Computer Sciences Purdue University Computer Sciences Building West Lafayette IN 47907 United States Department of Computer Science Haifa University Haifa 31905 Israel Department of Computer and Information Science Polytechnic University Six MetroTech Center Brooklyn NY 11201-3840 United States College of Computing Georgia Institute of Technology Atlanta GA 30332-0280 United States

We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S' is a substring of S, then the fingerprint of S' is the subset φ of Σ of precisely the symbols appearing in S'. In this paper we show efficient methods of answering various queries on fingerprint statistics. Our preprocessing is done in time O(n |Σ| log n log |Σ|) and enables answering the following queries: (1) Given an integer k, compute the number of distinct fingerprints of size k in time O(1). (2) Given a set φ ⊆ Σ, compute the total number of distinct occurrences in S of substrings with fingerprint φ in time O(| Σ| log n). © 2003 Elsevier B.V. All rights reserved.

关键词： Combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching

引用

INFORMATION PROCESSING LETTERS 2002年第1期83卷 33-39页

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

Let a text string T of n symbols and a pattern string P of m symbols from alphabet E be given. A swapped version P' of P is a length m string derived from P by a series of local swaps (i.e., p(l)' <-- p(l+1) and p(l+1)' <-- p(l)), where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i of T for which there exists a swapped version P' of P with an exact matching of P' in location i of T. Recently, some efficient algorithms were developed for this problem. Their time complexity is better than the best known algorithms for pattern matching with mismatches. However, the Approximate Pattern Matching with Swaps problem was not known to be solved faster than the Pattern Matching with Mismatches problem. In the Approximate Pattern Matching with Swaps problem the output is, for every text location i where there is a swapped match of P, the number of swaps necessary to create the swapped version that matches location i. The fastest known method to-date is that of counting mismatches and dividing by two. The time complexity of this method is O(nrootm log m) for a general alphabet Sigma. In this paper we show an algorithm that counts the number of swaps at every location where there is a swapped matching in time O (n log m log sigma), where sigma = min(m, \Sigma\). Consequently, the total time for solving the approximate pattern matching with swaps problem is O(f (n, m) + n log m log sigma), where f (n, in) is the time necessary for solving the Pattern Matching with Swaps problem. Since f (n, in) was shown to be O(n log m log a) this means our algorithm's running time is O(n log m log Q). (C) 2001 Elsevier Science B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm to generate all maximal cliques on trapezoid graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2002年第10期79卷 1057-1065页

作者： Bera, D Pal, M Pal, T Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India

In this paper, to find all maximal cliques of a trapezoid graph a set of intervals have been constructed by projecting the geometrical representation of the graph on the bottom line. The proposed algorithm for this pu... 详细信息

关键词： design and analysis of algorithms cliques maximal cliques trapezoid graphs

来源：评论

学校读者我要写书评

暂无评论

A speed-up for the commute between subword trees and DAWGs

引用

INFORMATION PROCESSING LETTERS 2002年第3期83卷 159-161页

作者： Apostolico, A Lonardi, S Univ Padua DEI I-35131 Padua Italy Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

A popular way to describe and build the DAWG or Directed Acyclic Word Graph of a string is by transformation of the corresponding subword tree. This transformation, which is not difficult to reverse, is easy to grasp and almost trivial to implement except for the assumed implication of a standard tree isomorphism algorithm. Here we point out a simple property of subword trees that makes checking tree isomorphism in this context a straightforward process, thereby simplifying the transformation significantly. Subword trees and DAWGs arise rather ubiquitously in applications of string processing, where they often play complementary roles. Efficient conversions are thus especially desirable. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： design and analysis of algorithms subword tree DAWG tree isomorphism test

来源：评论

学校读者我要写书评

暂无评论

Linear time algorithms on chordal bipartite and strongly chordal graphs

引用

29th International Colloquium on Automata, Languages and Programming

作者： Uehara, R Komazawa Univ Fac Nat Sci Tokyo Japan

ISBN: (纸本)3540438645

Chordal bipartite graphs axe introduced to analyze non-symmetric matrices, and form a large class of perfect graphs. There are several problems, which can be solved efficiently on the class using the characterization by the doubly lexical ordering of the bipartite adjacency matrix. However, the best known algorithm for computing the ordering runs in O(min{m log n,n(2)}), which is the bottleneck of the problems. We show a linear time algorithm that computes the ordering of a given chordal bipartite graph. The result improves the upper bounds of several problems, including recognition problem, from O(min{m log n, n(2)}) to linear time. Strongly chordal graphs are well-studied subclass of chordal graphs, and that have similar characterization. The upper bounds of several problems on a given strongly chordal graph are also improved from O(min {m log n, n(2)}) to linear time.

关键词： chordal bipartite graphs design and analysis of algorithms lexicographic breadth first search vertex elimination ordering strongly chordal graphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Uniquely restricted matchings

引用

ALGORITHMICA 2001年第2期31卷 139-154页

作者： Golumbic, MC Hirst, T Lewenstein, M Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel IBM Res Corp Yorktown Heights NY 10598 USA

A matching in a graph is a set of edges no two of which share a common vertex. In this paper we introduce a new, specialized type of matching which we call uniquely restricted matchings, originally motivated by the problem of determining a lower bound on the rank of a matrix having a specified zero/non-zero pattern. A uniquely restricted matching is defined to be a matching M whose saturated vertices induce a subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing a uniquely restricted matching and of finding a maximum uniquely restricted matching in a given graph, and present algorithms and complexity results for certain special classes of graphs. We demonstrate that testing whether a given matching M is uniquely restricted can be done in O (\M\\E\) time for an arbitrary graph G = (V, E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum uniquely restricted matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs.

关键词： graph theory perfect graphs design and analysis of algorithms matchings uniquely restricted matchings

来源：评论

学校读者我要写书评

暂无评论

An efficient bottom-up distance between trees 8

An efficient bottom-up distance between trees

引用

8th International Symposium on String Processing and Information Retrieval

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

ISBN: (纸本)0769511937

A new bottom-up distance measure for labeled trees, which is based on the largest common forest of the trees and has the threefold advantage of independence of particular edit costs, low complexity, and coverage of ordered and unordered trees, is introduced and related in this paper with other distance measures published in the literature. algorithms for computing the bottom-up distance in time linear in the number of nodes are given in full detail.

关键词： design and analysis of algorithms combinatorial problems graph algorithms pattern matching tree pattern matching tree isomorphism subtree isomorphism edit distance metric space largest common forest

来源：评论

学校读者我要写书评

暂无评论

New results on induced matchings

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期101卷 157-165页

作者： Golumbic, MC Lewenstein, M Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel

A matching in a graph is a set of edges no two of which share a common vertex. A matching M is an induced matching if no edge connects two edges of M. The problem of finding a maximum induced matching is known to be NP-Complete in general-and specifically for bipartite graphs and for 3-regular planar graphs. The problem has been shown to be polynomial for several classes of graphs. In this paper we generalize the results to:wider classes of graphs, and improve the time complexity of previously known results. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： graph theory perfect graphs design and analysis of algorithms matchings induced matchings strong matchings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：