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

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第1期35卷 82-99页

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

The importance of hypertext has been steadily growing over the past decade. The Internet and other information systems use hypertext formal, with data organized associatively rather than sequentially or relationally. A myriad of textual problems have been considered in the pattern matching field with many nontrivial results. Nevertheless, surprisingly little work has been done on the natural combination ol pattern matching and hypertext. Ln contrast to regular text, hypertext has a nonlinear structure and the techniques of pattern matching for text cannot be directly applied to hypertext. Manber and Wu (1992, "IAPR Workshop on Structural and Syntactic Pattern Recognition, Bern, Switzerland) pioneered the study of pattern matching in hypertext and defined a hypertext model for pattern matching. Akutsu (1993, "Procedures of the 4th Symposium on Combinatorial Pattern Matching Podova, Italy," pp. 1-10) developed an algorithm that can be used for exact pattern matching in a tree-structured hypertext. Park and I(im (1995, "6th Symposium on Combinatorial Pattern Matching;Helsinki, Finland") considered regular pattern matching in hypertext. They developed a complex algorithm that works for hypertext with an underlying structure of a DAG. In this paper we present a much simpler algorithm achieving the same complexity which runs on any hypertext graph. We then extend the problem to approximate pattern matching in hypertext, first considering hamming distance and then edit distance. We show that in contrast to regular text, it dos make a difference whether Che;errors occur in the hypertext or the pattern The approximate pattern matching problem in hypertext with errors in the hypertext turns out to be NP-complete anti the approximate pattern matching problem in hypertext: with errors in the pattern has a polynomial time solution, (C) 2000 Academic Press.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching hypertext pattern matching on hypertext.

来源：评论

学校读者我要写书评

暂无评论

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ü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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Area-Feature Boundary Labeling¹

引用

COMPUTER JOURNAL 2010年第6期53卷 827-841页

作者： Bekos, Michael A. Kaufmann, Michael Potika, Katerina Symvonis, Antonios Natl Tech Univ Athens Sch Appl Math & Phys Sci Athens 15780 Greece Univ Tubingen Inst Informat D-72076 Tubingen Germany

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical drawings, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site s is associated with an axis-parallel rectangular label l(s). The labels must be placed in distinct positions on the boundary of R and they must be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can 'float' within a polygonal region. We present a polynomial time algorithm, which runs in O(n(3)) time and produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of rectangle R.

关键词： boundary labeling map labeling design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

THE LONGEST COMMON SUBSEQUENCE PROBLEM REVISITED

引用

ALGORITHMICA 1987年第3期2卷 315-336页

作者： APOSTOLICO, A GUERRA, C Department of Computer Sciences Purdue University West Lafayette USA

This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn ≥m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherer≤mn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenr∼n, but it degrades to Θ(mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered ≤r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.

关键词： Characteristic tree design and analysis of algorithms Dictionary Dynamic programming Efficient merging of linear lists Finger-tree Longest common subsequence

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast computation of a longest increasing subsequence and application

引用

INFORMATION AND COMPUTATION 2010年第9期208卷 1054-1059页

作者： Crochemore, Maxime Porat, Ely Kings Coll London London WC2R 2LS England Univ Paris Est Paris France Bar Ilan Univ IL-52900 Ramat Gan Israel

We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, ..., n) can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log k). The algorithm also improves on the previous O(n log log n) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(n log log n)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. Crown Copyright (C) 2010 Published by Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms Longest increasing subsequence Longest common subsequence Data structures Priority queue Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期370卷 299-308页

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

Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we consider two descendent subtree-comparison problems on phylogenetic trees. Given a set of k phylogenetic trees whose leaves are drawn from {1, 2,..., n} and the leaves for two arbitrary trees are not necessary the same, we first present a linear-time algorithm to final all the maximal leaf-agreement descendent subtrees. Based on this result, we also present a linear-time algorithm to find all the maximal leaf-agreement isomorphic descendent subtrees. (c) 2006 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms phylogenetic trees maximal leaf-agreement descendent subtrees maximal leaf-agreernent isomorphic descendent subtrees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：