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

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.

来源：评论

学校读者我要写书评

暂无评论

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 1. Department of Computer Sciences Purdue University 47907 West Lafayette IN 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.

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2013年第6期E96A卷 1051-1058页

作者： Honma, Hirotoshi Nakajima, Yoko Aoshima, Haruka Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Kushiro Natl Coll Technol Elect Informat Syst Engn Course Kushiro Hokkaido 0840916 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph: Moreover, this algorithm can be implemented in O(log n) time with O(n/ log n) processors on EREW PRAM computation model.

关键词： design and analysis of algorithms intersection graphs circular trapezoid graphs spanning tree problem

来源：评论

学校读者我要写书评

暂无评论

Linear Time algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2013年第3期E96D卷 419-425页

作者： Honma, Hirotoshi Abe, Kodai Nakajima, Yoko Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Univ Tsukuba Dept Intelligent Interact Technol Tsukuba Ibaraki 3058577 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

Let G(s) = (V-s, E-s) be a simple connected graph. A vertex v is an element of V-s is an articulation vertex if deletion of v and its incident edges from G(s) disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u is an element of V-s is called a hinge vertex if there exist any two vertices x and y in G(s) whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.

关键词： design and analysis of algorithms articulation vertices hinge vertices circular permutation graphs

来源：评论

学校读者我要写书评

暂无评论

On computing longest paths in small graph classes

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2007年第5期18卷 911-930页

作者： Uehara, Ryuhei Uno, Yushi JAIST Sch Informat Sci Dept Informat Proc Ishikawa Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes.

关键词： algorithmic graph theory design and analysis of algorithms graph classes longest path problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：