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

An efficient label setting/correcting shortest path algorithm

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第1期51卷 437-455页

作者： Sedeno-Noda, Antonio Gonzalez-Martin, Carlos Univ La Laguna DEIOC Tenerife 38205 Spain

We design a new label shortest path algorithm by applying the concept of a pseudo permanent label. This approach allows an algorithm to partition the set of nodes into two new sets: pseudo permanently labeled nodes and its complementary set. From this point of view, this new label method can be considered as a label setting method. Moreover, at least one node becomes permanently labeled when some nodes which belong to the set of pseudo permanently labeled nodes are scanned in each iteration of the algorithm. In the case of networks with non-negative length arcs it is easy to prove that this node has the minimum distance label among the non-pseudo permanently labeled nodes. On the other hand, it is not known during the computation which pseudo permanently labeled nodes are permanently labeled. Therefore, all distance labels are temporary and the algorithm becomes a label correcting method. Nevertheless, the proposed algorithm exhibits some nice features, such as: (1) the time bound for the running of the algorithm for a network with n nodes and m arcs is O(nm);(2) the number of node scan operations in the algorithm is less than the number of these operations in the previous label correcting algorithms as is observed in the computational experience;(3) the algorithm incorporates two new rules which allow easy detection of a negative cycle in the network;(4) the algorithm is quite simple and very easy to implement, and does not require sophisticated data structures;(5) the algorithm exhibits flexibility in the order in which the new pseudo permanently labeled nodes are scanned. The above features are possible through the application of the pseudo permanent label concept.

关键词： Network/Graphs Distance algorithms design and analysis of algorithms Pseudo permanent labels

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT algorithms FOR FINDING THE MOST VITAL EDGE OF A MINIMUM SPANNING TREE

引用

INFORMATION PROCESSING LETTERS 1993年第5期48卷 211-213页

作者： IWANO, K KATOH, N KOBE UNIV COMMERCE DEPT MANAGEMENT SCINISHI KUKOBE 65121JAPAN

Let G = (V, E) be an undirected graph with m edges and n vertices such that each edge e has a real valued weight w(e). Let MST(G) be a minimum spanning tree in G. Let f(G) be the weight of a minimum spanning tree of G if G is connected;otherwise f(G) = infinity. We define a most vital edge with respect to a minimum spanning tree in a connected undirected graph G as an edge e such that f(G - e) greater-than-or-equal-to f(G - e') for every edge e' in G. In this paper, we give O(m + n log n) and O(ma(m, n)) time algorithms, which improve O(m log m) and O(n2) time bounds by Hsu et al. in Inform. Process. Lett. 39 (1991) 277-281.

关键词： design and analysis of algorithms MINIMUM SPANNING TREES MOST VITAL EDGES

来源：评论

学校读者我要写书评

暂无评论

STRINGS, TREES, AND PATTERNS

引用

INFORMATION PROCESSING LETTERS 1992年第3期41卷 157-161页

作者： VERMA, RM Department of Computer Science University of Houston Houston TX 77204 USA

In this paper we study subtree isomorphism and its relationships with some important symbolic problems. Recently, a linear time algorithm for ordered subtree isomorphism was given by Makinen. We note that a subtree of a rooted tree T, in Makinen's paper, refers to the tree rooted at any vertex in T. We consider ordered subtree isomorphism when a broader definition of subtree is used, viz., a subtree of T is any connected subgraph, including upsilon, of the tree rooted at any vertex-upsilon in T. We give some evidence to show that a linear time algorithm for this problem is unlikely. We also give an almost linear time reduction from the important problem of pattern matching to ordered subtree isomorphism. Finally, we present simpler linear time algorithms for ordered and unordered subtree isomorphism (with the more restrictive definition of subtree).

关键词： design and analysis of algorithms STRING MATCHING PATTERN MATCHING SUBTREE ISOMORPHISM

来源：评论

学校读者我要写书评

暂无评论

UNIFORM GENERATION OF FORESTS OF RESTRICTED HEIGHT

引用

INFORMATION PROCESSING LETTERS 1994年第6期50卷 323-327页

作者： ATKINSON, MD SACK, JR CARLETON UNIV SCH COMP SCIOTTAWA K1S 5B6ONTARIOCANADA UNIV ST ANDREWS DEPT MATH & COMPUTAT SCIST ANDREWS KY16 9SSFIFESCOTLAND

Tree structures occur throughout the theory of information storage. Typically each tree node contains some data and some pointers to other tree nodes. In most cases the number k of pointer fields is fixed and the structure is referred to as a k-way tree. An analysis considers k-way forests of fixed size (n), height (h), and number of components (c). The analysis gives a generator for producing such forests uniformly at random. Each random forest is generated in a linear number of operations in its size. The algorithm computes a table of values in a pre-processing phase. Each k-way forest is generated in time O(n). The method depends on a recurrence formula for the number of k-way forests of given size, height and number of components. It constructs the k-way forest level by level. The construction time for a level is dominated by the time required to choose the number of internal nodes on the level and the time required to obtain the nodes themselves.

关键词： RANDOM GENERATION design and analysis of algorithms TREES AND FORESTS

来源：评论

学校读者我要写书评

暂无评论

An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2011年第6期E94A卷 1381-1385页

作者： Honma, Hirotoshi Kitamura, Yutaro 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

In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an 0(n(2.68) + gamma n) time algorithm for solving the FVS problem on trapezoid graphs, where gamma is the total number of factors included in all maximal cliques.

关键词： design and analysis of algorithms feedback vertex set trapezoid graphs NP-hard

来源：评论

学校读者我要写书评

暂无评论

Data structures and algorithms for the string statistics problem

引用

ALGORITHMICA 1996年第5期15卷 481-494页

作者： Apostolico, A Preparata, FP UNIV PADUA DIPARTIMENTO ELETTRON & INFORMATI-35131 PADUAITALY BROWN UNIV DEPT COMP SCIPROVIDENCERI 02912

Given a textstring x of length n, the Minimal Augmented Suffix Tree (T) over cap (x) of x is a digital-search index that returns, for any query string w and in a number of comparisons bounded by the length of w, the maximum number of nonoverlapping occurrences of w in x. It is shown that, denoting the length of x by n, (T) over cap (x) can be built in time O(n log(2) n) and space O(n log n), off-line on a RAM.

关键词： design and analysis of algorithms combinatorics on strings pattern matching substring statistics suffix tree augmented suffix tree period of a string repetition in a string

来源：评论

学校读者我要写书评

暂无评论

A quadratic time 2-approximation algorithm for block sorting

引用

THEORETICAL COMPUTER SCIENCE 2009年第8-10期410卷 711-717页

作者： Bein, Wolfgang W. Larmore, Lawrence L. Morales, Linda Sudborough, I. Hal Univ Texas Richardson Dept Comp Sci Richardson TX 75083 USA Univ Nevada Sch Comp Sci Ctr Adv Study Algorithms Las Vegas NV 89154 USA

The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O(n(2)). The approximation algorithm is based oil the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O(n(2)) time, even though block sorting is known to be N P-hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology. (C) 2009 Published by Elsevier B.V.

关键词： design and analysis of algorithms Approximation algorithms Block sorting Transposition sorting Optical character recognition

来源：评论

学校读者我要写书评

暂无评论

The multi-budgeted and weighted bounded degree metric Steiner network problem

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2017年 104卷 36-48页

作者： Stamoulis, Georgios Maastricht Univ Dept Data & Knowledge Engn DKE POB 616 NL-6200 MB Maastricht Netherlands

We study the multi-budgeted version of the metric Survivable Network design Problem (SND) (Jain, 2001), also known as Steiner Network problem, where besides the usual connectivity requirements (i.e., lower bound on the number edge-disjoint paths) between pre-specified pairs of points, we are also asked to satisfy a set of extra linear constraints (the budgets). Based on combinatorial properties of extreme point solutions of the natural LP relaxation of the problem and using the iterative method, we design new approximation algorithms with the following performance guarantee: if any edge participates in at most f is an element of N budgets, then we show how we can device an (f + 2,f + 2) bi-criteria approximation algorithm in polynomial time i.e., return a solution with cost at most (2 + f) times the optimal one with a potential budget overflow bounded from above by the same factor. In other words, the approximation and budget violation guarantee we achieve is a linear function of the maximum frequency among all the edges in the budgets, as opposed to a function of the number of budgets themselves and this constitutes a strict improvement over the previous approaches. Our approach is flexible enough and we demonstrate how it can be used to provide a (4, 4) bi-criteria algorithm for the Minimum Weighted Bounded Degree version of the SND problem in which we have the standard SND connectivity constraints and, additionally, for every vertex v in the graph we have an upper bound on the sum of the weights of the edges incident to that edge in any feasible solution. These problems, besides their obvious theoretical interest, have numerous real life applications from Cloud Computing to Optical Networking systems. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Survivable Network design design and analysis of algorithms Fault tolerant computing Cloud Computing Communication networks

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching

引用

INFORMATION PROCESSING LETTERS 2002年第1期83卷 33-39页

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Atlanta GA 30332 USA Weizmann Inst Sci IL-76100 Rehovot Israel

Let a text string T of n symbols and a pattern string P of m symbols from alphabet E 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(nrootm 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 sigma), where f (n, in) is the time necessary for solving the Pattern Matching with Swaps problem. Since f (n, in) was shown to be O(n log m log a) this means our algorithm's running time is O(n log m log Q). (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps non-standard pattern matching approximate pattern matching

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：