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

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

来源：评论

学校读者我要写书评

暂无评论

Pattern matching in hypertext

引用

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.

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching 20th

引用

20th Conference on Foundations of Software Technology and Theoretical Computer Science

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

ISBN: (纸本)3540414134

Let a text string T of n symbols and a pattern string P of rn symbols from alphabet Sigma 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(n rootm 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 a), where f (n, m) is the time necessary for solving the pattern matching with swaps problem.

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

来源：评论

学校读者我要写书评

暂无评论

Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs

引用

SIAM JOURNAL ON COMPUTING 1999年第5期28卷 1906-1922页

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

We study the parameterized complexity of three NP-hard graph completion problems. The minimum fill-in problem asks if a graph can be triangulated by adding at most k edges. We develop O(c(k)m) and O(k(2)mn + f(k)) algorithms for this problem on a graph with n vertices and m edges. Here f(k) is exponential in k and the constants hidden by the big-O notation are small and do not depend on k. In particular, this implies that the problem is fixed-parameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biology, asks if a graph can be made proper interval by adding no more than k edges. We show that the problem is FPT by providing a simple search-tree-based algorithm that solves it in O(c(k)m)-time. Similarly, we show that the parameterized version of the strongly chordal graph completion problem is FPT by giving an O(c(k)m log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions within the same time bounds.

关键词： design and analysis of algorithms parameterized complexity chordal graphs proper interval graphs strongly chordal graphs minimum fill-in physical mapping of DNA

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm to generate all maximal independent sets on trapezoid graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1999年第4期70卷 587-599页

作者： Hota, M Pal, M Pal, TK Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India Midnapore Coll Dept Math Midnapore 721101 India

Generation of all maximal independent sets (MIS) is a NP-complete problem for general graphs. In this paper, using a particular geometric property of trapezoid graph, an efficient algorithm is designed which enables to generate an maximal independent sets for a trapezoid graph in O(n (m) over bar + alpha n) time, where (m) over bar and alpha are respectively the number of edges of the complement graph of the given graph and the number of generated maximal independent sets. There is no prior algorithm available to solve this problem of finding all MIS for trapezoid graphs.

关键词： design and analysis of algorithms data structure independent sets trapezoid graph tree

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Computational Study of Routing algorithms for Realistic Transportation Networks

引用

ACM Journal of Experimental Algorithmics 1999年 4卷 6-6页

作者： Jacob, Riko Marathe, Madhav Nagel, Kai RRTCS Department of Computer Science University of Aarhus DK-8000 Århus C Ny Munkegade Bldg. 540 Denmark Los Alamos National Laboratory MS M997 Los Alamos NM 87545 P.O. Box 1663 United States

We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation analysis and SIMulation System) project. The main focus of the paper is to study how various heuristic as well as exact solutions and associated data structures affect the computational performance of the software developed for realistic transportation networks. For this purpose we have used a road network representing, with high degree of resolution, the Dallas Fort-Worth urban area. We discuss and experimentally analyze various one-to-one shortest-path algorithms. These include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances. Computational results are provided to compare empirically the efficiency of various algorithms. Our studies indicate that a modified Dijkstra's algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies. © 1999, ACM. All rights reserved.

关键词： design and analysis of algorithms Experimental analysis Network design Shortest-Paths algorithms Transportation Planning

来源：评论

学校读者我要写书评

暂无评论

On minimum-area hulls

引用

ALGORITHMICA 1998年第1期21卷 119-136页

作者： Arkin, EM Chiang, YJ Held, M Mitchell, JSB Sacristan, V Skiena, SS Yang, TC SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA Salzburg Univ Inst Comp Wissensch A-5020 Salzburg Austria Univ Politecn Catalunya Dept Matemat Applicada 2 E-08028 Barcelona Spain SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Kyungsung Univ Dept Comp Sci & Stat Nam Gu Pusan 608736 South Korea

We study some minimum-area hull problems that generalize the notion of convex hull to starshaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n-vertex simple polygon P, find a minimum-area, star-shaped polygon P* containing P. This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P* are constrained to be vertices of P, and the unrestricted version, in which the vertices of P* can be anywhere in the plane. We prove that the restricted problem falls in the class of "3SUM-hard" (sometimes called "n(2)-hard") problems, which are suspected to admit no solutions in o(n(2)) time. Further, we give an O(n(2)) time algorithm, improving the previous bound of O(n(5)). We also show that the unrestricted problem can be solved in O(n(2)p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O (n). We also consider the case in which P* is required to be monotone, with respect to an unspecified direction;we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of O (n log n) time for computing P* in the restricted version, and an upper bound of O (nq(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n).

关键词： minimum-area hulls star-shaped polygons monotone polygons 3SUM-hardness lower bounds computational geometry design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：