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

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

来源：评论

学校读者我要写书评

暂无评论

On the Longest Common Cartesian Substring Problem^†

引用

COMPUTER JOURNAL 2023年第4期66卷 907-923页

作者： Faro, Simone Lecroq, Thierry Park, Kunsoo Scafiti, Stefano Univ Catania Dept Math & Comp Sci Catania Italy Normandie Univ UNIROUEN LITIS F-76000 Rouen France Seoul Natl Univ Seoul South Korea

A Cartesian tree is associated with a string of numbers and is structured as a heap from which the original string can be recovered. Although Cartesian trees have been introduced 40 years ago, the Cartesian tree matching problem appeared very recently. It consists in finding all substrings of given text, which have the same Cartesian tree as that of a given pattern. In this paper, we address the problem of computing the longest common Cartesian substrings of two strings and present three methods for such problem. Our first method is based on a classical suffix tree construction and solves the problem in randomized linear time and linear space, although the space overhead is quite prohibitive in the case of large strings. Our second solution is based on classical dynamic programming, and our third solution is based on a constructive approach. Both of them run in quadratic worst case time but are more space economical in practice. From our experimental results, it turns out that our second solution runs faster than the standard suffix tree solution for short strings, whereas our third solution is more suitable for large strings, when storing a full suffix tree becomes prohibitive.

关键词： Cartesian tree non-standard string matching longest common substring combinatorial algorithm design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Pattern matching with swaps

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第2期37卷 247-266页

作者： Amir, A Aumann, Y Landau, GM Lewenstein, M Lewenstein, N Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Atlanta GA 30332 USA Polytech Univ MetroTech Ctr 6 Dept Comp & Informat Sci Brooklyn NY 11201 USA Univ Haifa Dept Comp Sci IL-31905 Haifa Israel

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Sigma be given. A swapped version T' of T is a length n string derived from T by a series of local swaps (i.e., t(l)' <-- t(l+1) and t(l+1)' <-- t(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 for which there exists a swapped version T' of T with an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We present an algorithm whose time complexity is O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). (C) 2000 Academic Press.

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

来源：评论

学校读者我要写书评

暂无评论

Constructing independent spanning trees for locally twisted cubes

引用

THEORETICAL COMPUTER SCIENCE 2011年第22期412卷 2237-2252页

作者： Liu, Yi-Jiun Lan, James K. Chou, Well Y. Chen, Chiuyuan Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4;therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n);consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Independent spanning trees Data broadcasting design and analysis of algorithms Locally twisted cubes Hypercubes Hypercube variants Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

The interval-merging problem

引用

INFORMATION SCIENCES 2007年第2期177卷 519-524页

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

A closed interval is an ordered pair of real numbers [x, y], with x <= y. The interval [x,y] represents the set {i is an element of R\x <= i <= y}. Given a set of closed intervals J = {[a(1), b(1)], [a(2), b(2)]...., [a(k), b(k)]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(J) = {[x(1), y(1)], [x(2), y(2)],..., [x(j), y(j)]}, j <= k, such that the real numbers represented by J = boolean OR(k)(i=1) [a(i), b(i)] equal those represented by M (J) = boolean OR(j)(i=1) [x(i), y(i)]. In this paper, we show the problem can be solved in O(dlog d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of J. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(logd) parallel time using O(d/logd) processors on an EREW PRAM. (C) 2006 Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms parallel algorithms data structures interval-merging PRAM

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Corona Training Protocols in Wireless Sensor and Actor Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2009年第8期20卷 1216-1230页

作者： Barsi, Ferruccio Bertossi, Alan A. Sorbelli, Francesco Betti Ciotti, Roberto Olariu, Stephan Pinotti, M. Cristina Univ Perugia Dept Math & Comp Sci I-06123 Perugia Italy Univ Bologna Dept Comp Sci I-40127 Bologna Italy Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA

Scalable energy-efficient training protocols are proposed for wireless networks consisting of sensors and a single actor, where the sensors are initially anonymous and unaware of their location. The protocols are based on an intuitive coordinate system imposed onto the deployment area, which partitions the sensors into clusters. The protocols are asynchronous, in the sense that the sensors wake up for the first time at random, then alternate between sleep and awake periods both of fixed length, and no explicit synchronization is performed between them and the actor. Theoretical properties are stated under which the training of all the sensors is possible. Moreover, both worst-case and average case analyses of the performance, as well as an experimental evaluation, are presented showing that the protocols are lightweight and flexible.

关键词： Wireless sensor networks actors corona training localization network protocols design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A weak approach to suffix automata simulation for exact and approximate string matching

引用

THEORETICAL COMPUTER SCIENCE 2022年 933卷 88-103页

作者： Faro, Simone Scafiti, Stefano Univ Catania Dept Math & Comp Sci Viale A Doria 6 I-95125 Catania Italy

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton, a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. Experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Exact string matching Swap matching Text processing Automata Experimental algorithms design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：