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

dynamic and Internal Longest Common Substring

ALGORITHMICA 2020年第12期82卷 3707-3743页

作者： Amir, Amihood Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands Univ Warsaw Inst Informat Warsaw Poland Samsung R&D Inst Poland Warsaw Poland

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n)-time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to the fully dynamic LCS problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in (O) over tilde (n(2/3)) time, after (O) over tilde (n)-time and space preprocessing. This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, the authors presented an (O) over tilde (n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in (O) over tilde (1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings;specifically, computing the longest palindrome and the Lyndon factorization of a string after a single edit operation. We develop dynamic sublinear-time algorithms for both of these problems as well. We also consider internal LCS queries, that is, queries in which we are to return an LCS of a pair of substrings of S and T. We show that answering such queries is hard in general and propose efficient data structures for several restricted cases.

关键词： Longest common substring String algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic GRAPH DRAWINGS - TREES, SERIES-PARALLEL DIGRAPHS, AND PLANAR ST-DIGRAPHS

引用

SIAM JOURNAL ON COMPUTING 1995年第5期24卷 970-1001页

作者： COHEN, RF DIBATTISTA, G TAMASSIA, R TOLLIS, IG UNIV ROMA LA SAPIENZA DIPARTIMENTO INFORMAT & SISTEMIST I-00198 ROME ITALY INT COMP SCI INST BERKELEY CA 94704 USA BROWN UNIV DEPT COMP SCI PROVIDENCE RI 02912 USA UNIV TEXAS DEPT COMP SCI RICHARDSON TX 75083 USA

Drawing graphs is an important problem that combines elements of computational geometry and graph theory. Applications can be found in a variety of areas including circuit layout, network management, software engineering, and graphics. The main contributions of this paper can be summarized as follows: We devise a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing, and we show its applications. We present efficient dynamic drawing algorithms for trees and series-parallel digraphs. As further applications of the model, we give dynamic drawing algorithms for planar st-digraphs and planar graphs. Our algorithms adopt a variety of representations (e.g., straight line, polyline, visibility) and update the drawing in a smooth way.

关键词： GRAPH DRAWING dynamic algorithms DATA STRUCTURES LAYOUT TREES SERIES-PARALLEL DIGRAPHS PLANAR GRAPHS

来源：评论

学校读者我要写书评

暂无评论

dynamic generation of discrete random variates

引用

THEORY OF COMPUTING SYSTEMS 2003年第4期36卷 329-357页

作者： Matias, Y Vitter, JS Ni, WC Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Purdue Univ Dept Comp Sci W Lafayette IN USA TBCommerce Network Corp Pomona CA 91768 USA

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in O(log* N) expected time and updates a weight in O(2(log)* (N)) expected time in the worst case. We then show how to reduce the update time to O(log* N) amortized expected time. We finally show how to apply our techniques to a lookup-table technique in order to obtain expected constant time in the worst case for generation and update. We give parallel algorithms for parallel generation and update having optimal processor-time product. Besides the usual application in computer simulation, our method can be usedto perform constant-time prediction in prefetching applications. We also apply our techniques to obtain an efficient dynamic algorithm for maintaining an approximate heap of N elements, in which each query is required to return an element whose value is within an epsilon multiplicative factor of the maximal element value. For epsilon = 1/polylog(N), each query, insertion, or deletion takes O(log log log N) time.

关键词： logs refresh time algorithms Elements Computer Simulation nitrogen dynamic algorithms logarithm (log) Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A FULLY dynamic REACHABILITY ALGORITHM FOR DIRECTED GRAPHS WITH AN ALMOST LINEAR UPDATE TIME

引用

SIAM JOURNAL ON COMPUTING 2016年第3期45卷 712-733页

作者： Roditty, Liam Zwick, Uri Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m + n log n) and a worst-case query time of O(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting "retrospectiveness" property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O(m alpha(n)) amortized time, and each query in O(1) worst-case time, where alpha(n) is a functional inverse of Ackermann's function appearing in the analysis of the Union-Find data structure. Note that the update time of O(m alpha(n)), in the case of a delete operation, is the time needed for updating all versions of the graph.

关键词： graph algorithms dynamic algorithms transitive closure

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially dynamic Networks

引用

ACM TRANSACTIONS ON algorithms 2017年第4期13卷 1–24页

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci Wahringer Str 29 A-1060 Vienna Austria Salzburg Univ Dept Comp Sci Jakob Haringer Str 2 A-5020 Salzburg Austria KTH Royal Inst Technol Sch Comp Sci & Commun CSC Lindstedtsvagen 3 SE-10044 Stockholm Sweden

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1 + is an element of)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. Our technique also leads to a deterministic (1 + is an element of)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011;Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.

关键词： Distributed algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

A loop-free shortest-path routing algorithm for dynamic networks

引用

THEORETICAL COMPUTER SCIENCE 2014年 516卷 1-19页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Univ Perugia Dept Math & Informat I-06123 Perugia Italy Univ Laquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy

This work introduces Loop-Free Routing (LFR), a new loop-free distance-vector routing algorithm, which is able to update the shortest paths of a distributed network in fully dynamic scenarios. This work also provides an evaluation based on simulations of LFR and Diffuse Update ALgorithm (DUAL), one of the most popular loop-free distance-vector algorithms, which is part of CISCO's widely used Enhanced Interior Gateway Routing Protocol (EIGRP). The simulations are performed on dynamic scenarios based on both real-world and controlled instances. The simulations show that LFR is always the best choice in terms of memory requirements, while in terms of messages sent LFR outperforms DUAL on real-world networks, whereas DUAL is the best choice on controlled scenarios. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Distributed networks Loop-free routing Shortest-path dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast dynamic Transitive Closure with Lookahead

引用

ALGORITHMICA 2010年第2期56卷 180-197页

作者： Sankowski, Piotr Mucha, Marcin Warsaw Univ Inst Informat PL-02097 Warsaw Poland

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n(omega(1,1,epsilon)-epsilon)) time given a lookahead of n(epsilon) operations, where omega(1,1,epsilon) is the exponent of multiplication of n x n matrix by n x n(epsilon) matrix. For epsilon <= 0.294 we obtain an algorithm with queries and updates in O(n(2-epsilon)) time, whereas for epsilon = 1 the time is O(n(omega-1)). This is essentially optimal as it implies an O(n(omega)) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n(omega/2)) time to process n(1/2) operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.

关键词： Transitive closure dynamic algorithms Lookahead Algebraic algorithms Matrix inverse Planar graphs

来源：评论

学校读者我要写书评

暂无评论

New amortized cell-probe lower bounds for dynamic problems

引用

THEORETICAL COMPUTER SCIENCE 2019年 779卷 72-87页

作者： Bhattacharya, Sayan Henzinger, Monika Neumann, Stefan Univ Warwick Warwick England Univ Vienna Fac Comp Sci Vienna Austria

We build upon the recent papers by Weinstein and Yu [11], Larsen [7], and Clifford et al. [3] to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results. 1. For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size n(l+Omega(1)) and has degree n, any dynamic data structure must either have an amortized update time of Omega((Ign/ IgIgn)(2)) or an amortized query time of Omega((lgn/IgIgn)(2)). 2. For the dynamic online matrix vector multiplication problem, where we get an n x n matrix whose entires are drawn from a finite field of size ne(1), any dynamic data structure must either have an amortized update time of Omega((lgn/ lgIgn)(2)) or an amortized query time of Omega(n . (Ign/ Ig Ign)(2)). For these two problems, the previous works by Larsen [7] and Clifford et al. [3] gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model. (C) 2019 Elsevier B.V. All rights reserved.

关键词： dynamic algorithms Cell-probe lower bounds Polynomial evaluation Online matrix vector multiplication

来源：评论

学校读者我要写书评

暂无评论

dynamic word problems

引用

JOURNAL OF THE ACM 1997年第2期44卷 257-271页

作者： Frandsen, GS Miltersen, PB Skyum, S University of Aarhus Aarhus Denmark

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x = (x(1), x(2),..., x(n)) is an element of M-n, initially (1, 1,..., 1), with two kinds of operations, for each i is an element of (1,..., n) and a is an element of M, an operation change(i,a), which changes x(i) to a and a single operation product returning IIi=1n x(i). This is the dynamic word problem for M. If we in addition for each j is an element of (1,..., n) have an operation prefix, returning IIi=1j x(i), we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a partial classification of the complexity based on algebraic properties of M.

关键词： cell probe model dynamic algorithms Krohn-Rhodes decomposition sunflower lemma word problems

来源：评论

学校读者我要写书评

暂无评论

On dynamic Shortest Paths Problems

引用

ALGORITHMICA 2011年第2期61卷 389-401页

作者： Roditty, Liam Zwick, Uri Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain the following results related to dynamic versions of the shortest-paths problem: (i) Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems. (ii) A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of (O) over tilde (m root n) (we use (O) over tilde to hide small poly-logarithmic factors) and a worst case query time is O(n(3/4)). (iii) A deterministic O(n(2)log n) time algorithm for constructing an O(log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.

关键词： dynamic algorithms Graph Shortest paths Spanners

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：