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

Approximate Pattern Matching with the L₁, L₂ and L∞ Metrics

ALGORITHMICA 2011年第2期60卷 335-348页

作者： Lipsky, Ohad Porat, Ely Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

Given an alphabet I ={1,2 pound,aEuro broken vertical bar,|I |} pound text string TaI pound (n) and a pattern string PaI pound (m) , for each i=1,2,aEuro broken vertical bar,n-m+1 define L (p) (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L (p) distance is to compute L (p) (i) for every i=1,2,aEuro broken vertical bar,n-m+1. We discuss the problem for d=1,2,a. First, in the case of L (1) matching (pattern matching with an L (1) distance) we show a reduction of the string matching with mismatches problem to the L (1) matching problem and we present an algorithm that approximates the L (1) matching up to a factor of 1+epsilon, which has an O (1/epsilon 2nlogm log vertical bar Sigma vertical bar) run time. Then, the L (2) matching problem (pattern matching with an L (2) distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L (a) matching up to a factor of 1+epsilon with a run time of O (1/epsilon 2nlogm log vertical bar Sigma vertical bar). We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog (4) m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.

关键词： design and analysis of algorithms Combinatorial algorithms on words Approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Determining approximate shortest paths on weighted polyhedral surfaces

引用

JOURNAL OF THE ACM 2005年第1期52卷 25-53页

作者： Aleksandrov, L Maheshwari, A Sack, JR Bulgarian Acad Sci IPOI BU-1113 Sofia Bulgaria Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter E, 0 < epsilon < 1, the cost of the computed paths is at most 1 + epsilon times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P)(n)/(rootepsilon) log (n)/(epsilon) log (1)/(epsilon)) time, where C(P) captures geometric parameters and the weights of the faces of P.

关键词： algorithms design performance design and analysis of algorithms computational geometry approximation algorithms shortest path problems polyhedral surfaces weighted paths

来源：评论

学校读者我要写书评

暂无评论

Bounded degree interval sandwich problems

引用

ALGORITHMICA 1999年第2期24卷 96-104页

作者： Kaplan, H Shamir, R AT&T Bell Labs Res Florham Park NJ 07932 USA Tel Aviv Univ Sackler Fac Exact Sci Dept Comp Sci IL-69978 Tel Aviv Israel

The problems of Interval Sandwich (IS)and Intervalizing Colored Graphs' (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous data. Most of the results obtained so far on the problems were hardness results. Here we study the problems under assumptions of sparseness, which hold in the biological context. We prove that both problems are polynomial when either (1) the input graph degree and the solution graph clique size are bounded, or (2) the solution graph degree is bounded. In particular, this implies that ICC is polynomial on bounded degree graphs for every fixed number of colors, in contrast with the recent result of Bodlaender and de Fluiter.

关键词： interval graphs computational biology parametrized complexity design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Paging mobile users in cellular networks: Optimality versus complexity and simplicity

引用

THEORETICAL COMPUTER SCIENCE 2013年 470卷 23-35页

作者： Bar-Noy, Amotz Cheilaris, Panagiotis Feng, Yi Golin, Mordecai J. CUNY Dept Comp Sci New York NY 10016 USA Univ Svizzera Italiana Fac Informat Lugano Switzerland Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Hong Kong Peoples R China

A mobile user is roaming in a zone composed of many cells in a cellular network system. When a call arrives, the system pages the user in these cells since the user never reports its location unless it leaves the zone. Each cell is associated with a positive value which is the probability that the user resides in this cell. A delay constraint requires the user to be found within a predetermined number of paging rounds where in each round a subset of the cells is paged. The goal is to design a paging strategy that minimizes the expected number of paged cells until the user is found. Optimal solutions based on dynamic programming are known. The running time of former implementations is quadratic in the number of cells and linear in the number of rounds. We introduce two implementations whose running times are also linear in the number of cells, by proving that the dynamic programming formulation satisfies properties (like the Monge property) that enable us to use various dynamic programming speed-up techniques. We also propose a new heuristic of almost linear complexity that outperforms a known linear complexity heuristic while running faster when the number of rounds is far less than the number of cells. Our comprehensive simulations compare the non-optimal heuristics with the optimal solutions, demonstrating the trade-off between optimality and running time efficiency as well as implementation simplicity. (C) 2012 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms Partitioning and scheduling

来源：评论

学校读者我要写书评

暂无评论

K-VIOLATION LINEAR-PROGRAMMING

引用

INFORMATION PROCESSING LETTERS 1994年第2期52卷 109-114页

作者： ROOS, T WIDMAYER, P Department Informatik ETH Zentrum CH-8092 Z&uuml rich Switzerland

We introduce the notion of k-violation linear programming. Given a set of n halplanes, we want to compute an optimal solution with respect to a given linear functional. However, in opposite to classical linear programming [16], we allow to violate at most k of the n constraints, for some fixed k is an element of {0,...,n-1}. We solve this problem in O(beta(k)(n) time and O(n) space, where beta(k)(n) := n log + k log(2) k. This is optimal if k is an element of O(n(alpha)) for any fixed positive alpha < 1. The general idea behind our approach is a new approach is a new technique for computing a minimum of the k-level of an arrangement. Based on recent slope selecting techniques by Cole et al. [4] and Matousek [15], we develop an algorithm for computing a minimum k-level point in O(beta(k)(n)) time and linear space. Our result improves all existing approaches that explicitly compute the entire k-level [3,9,11]. The presented technique is of independent interest and can be applied to several other problems, as well.

关键词： design and analysis of algorithms COMBINATORIAL PROBLEMS COMPUTATIONAL GEOMETRY LINEAR PROGRAMMING

来源：评论

学校读者我要写书评

暂无评论

The complexity of certain incremental code generation problems

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1999年第4期71卷 447-458页

作者： Venugopal, R Srikant, YN Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

关键词： compilers design and analysis of algorithms incremental algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Realizing degree sequences in parallel

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1996年第2期9卷 317-338页

作者： Arikati, SR Maheshwari, A MPI Informatik 66123 Saarbrücken Im Stadtwald Germany MPI Informatik Germany School of Computer Science Carleton University Ottawa Ont. K1S 5B6 Canada

A sequence d of integers is a degree sequence if there exists a (simple) graph G such that the components of d are equal to the degrees of the vertices of G. The graph G is said to be a realization of d. We provide an efficient parallel algorithm to realize d;the algorithm runs in O(log n) time using O(n + m) CRCW PRAM processors, where n and m are the number of vertices and edges in G. Before our result, it was not known if the problem of realizing d is in NC.

关键词： design and analysis of algorithms parallel computation graph algorithms degree sequence majorization PRAM

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm to generate all maximal independent sets on permutation graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1998年第3-4期67卷 261-274页

作者： Pal, M Indian Inst Technol Dept Math Kharagpur 721302 W Bengal India

In this paper, an O(log n) time and O(nn'/log n) processors parallel algorithm is designed to generate all paths from leaf nodes to the root of a tree, where n' is the total number of such paths. Using this algorithm an O(log N) time and O((n(2)+N)/log n) processors parallel algorithm is designed to generate all maximal independent sets on permutation graphs, where n represents the number of vertices (nodes) N is the output size. Both the algorithms run on an EREW PRAM.

关键词： data structure design and analysis of algorithms parallel algorithms independent sets cliques permutation graph tree

来源：评论

学校读者我要写书评

暂无评论

Weight-constrained and density-constrained paths in a tree: Enumerating, counting, and k-maximum density paths

引用

DISCRETE APPLIED MATHEMATICS 2015年 180卷 126-134页

作者： Lee, Chia-Wei Chen, Pin-Liang Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan Natl Cheng Kung Univ Inst Med Informat Tainan 701 Taiwan Natl Cheng Kung Univ Inst Mfg Informat & Syst Tainan 701 Taiwan

Let T be a tree of n nodes in which each edge is associated with a value and a weight that are a real number and a positive integer, respectively. Given two integers W-min and W-max and two real numbers d(min) and d(max) a path P in a tree is feasible if the sum of the edge weights in P is between W-min and W-max and the ratio of the sum of the edge values in P to the sum of the edge weights in P is between dmin and dm. In this paper, we first present an O(n log(2) n+ h)time algorithm to find all feasible paths in a tree, where h = O(n(2)) if the output of a path is given by its end-nodes. Then, we present an O(n log(2) n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(n log(2) n + h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Counting mode design and analysis of algorithms Feasible paths k-maximum density path problem Network design Trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：