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

Fully dynamic algorithms for maintaining shortest paths trees

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第2期34卷 251-281页

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Rome Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the update procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms require O(root m log n) worst case time per output update. We also show that, if insertions and deletions of edges are allowed, then similar amortized bounds hold. (C) 2000 Academic Press.

关键词： Computational-complexity Planar graphs Combinatorial Digraphs complexity classes Paths Byways Bounded deletions search time Edges dynamic algorithms directed graphs Output planning drawings

来源：评论

学校读者我要写书评

暂无评论

The delaunay hierarchy

引用

International Journal of Foundations of Computer Science 2002年第2期13卷 163-180页

作者： Devillers, Olivier INRIA BP93 06902 Sophia Antipolis France

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and the possibility of fully dynamic insertions and deletions. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the level below. Point location is done by walking in a triangulation to determine the nearest neighbor of the query at that level, then the walk restarts from the neighbor at the level below. Using a small subset (3%) to sample a level allows a small memory occupation;the walk and the use of the nearest neighbor to change levels quickly locate the query. © 2002 World Scientific Publishing Company.

关键词： computational geometry Delaunay triangulation dynamic algorithms geometric computing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Union and split operations on dynamic trapezoidal maps

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第3-4期17卷 153-163页

作者： Teillaud, M INRIA F-06902 Sophia Antipolis France

We propose algorithms to perform two new operations on an arrangement of line segments in the plane, represented by a trapezoidal map: the split of the map along a given vertical line D, and the union of two trapezoidal maps computed in two vertical slabs of the plane that are adjacent through a vertical line D. The data structure we use is a modified Influence Graph, still allowing dynamic insertions and deletions of line segments in the map. The algorithms for both operations run in O(s(D) log n + log(2) n) time, where n is the number of line segments in the map, and so is the number of line segments intersected by D. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： dynamic algorithms randomized algorithms data structures parallel data structures trapezoidal map

来源：评论

学校读者我要写书评

暂无评论

The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. Odd case

引用

SIAM JOURNAL ON COMPUTING 2000年第3期30卷 753-808页

作者： Dinitz, Y Vainshtein, A Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Haifa Dept Math IL-31905 Haifa Israel Univ Haifa Dept Comp Sci IL-31905 Haifa Israel

Let G = (V, E) be an undirected graph, S be a subset of its vertices, C-S be the set of minimum edge-cuts partitioning S, and S be the cardinality of such a cut. We suggest a graph structure, called the connectivity carcass of S, that represents both cuts in CS and the partition of V by all these cuts;its size is O(min{\E\, lambda(S)\V\}). In this paper we present general constructions and study in detail the case lambda(S) odd;the specifics of the case S even are considered elsewhere. For an adequate description of the connectivity carcass we introduce a new type of graph: locally orientable graphs, which generalize digraphs. The connectivity carcass consists of a locally orientable quotient graph of G, a cactus tree (in case S odd, just a tree) representing all distinct partitions of S by cuts in C-S, and a mapping connecting them. One can build it in O (\S\) max-flow computations in G. For an arbitrary sequence of u edge insertions not changing lambda(S), the connectivity carcass can be maintained in time O (\V\ min {\E\, lambda(S) \V\} + u). For two vertices of G, queries asking whether they are separated by a cut in C-S are answered in O(1) worst-case time per query. Another possibility is to maintain the carcass in O (\S\ min {\E\, lambda(S) \V\} + u) time, but to answer the queries in O(1) time only if at least one of the vertices belongs to S.

关键词： edge-connectivity minimum cuts graph structures incremental maintenance dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamically switching vertices in planar graphs

引用

ALGORITHMICA 2000年第1期28卷 76-103页

作者： Frigioni, D Italiano, GF Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Roma Tor Vergata Dipartimento Sistemi & Prod Rome Italy

We consider graphs whose vertices may be in one of two different states: either on or off. We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off, and may insert a new edge or delete an existing edge. A query tests whether any two given vertices are connected in the subgraph induced by the vertices that are on. We give efficient algorithms that maintain information about connectivity on planar graphs in O(log(3) n) amortized time per query, insert, delete, switch-on, and switch-off operation over sequences of at least Omega(n) operations, where n is the number of vertices of the graph.

关键词： planar graphs dynamic algorithms connectivity separators

来源：评论

学校读者我要写书评

暂无评论

Experimental Analysis of dynamic algorithms for the Single Source Shortest Paths Problem

引用

ACM Journal of Experimental Algorithmics 1998年 3卷 5-5页

作者： Frigioni, Daniele loffreda, Mario Nanni, Umberto Pasqualone, Giulio Univ. di Roma “La Sapienza”

In this paper we propose the first experimental study of the fully dynamic single-source shortest-paths problem on directed graphs with positive real edge weights. In particular, we perform an experimental analysis of three different algorithms: Dijkstra's algorithm, and the two output bounded algorithms proposed by Ramalingam and Reps in [30] and by Frigioni, Marchetti-Spaccamela and Nanni in [18], respectively. The main goal of this paper is to provide a first experimental evidence for: (a) the effectiveness of dynamic algorithms for shortest paths with respect to a traditional static approach to this problem;(b) the validity of the theoretical model of output boundedness to analyze dynamic graph algorithms. Beside random generated graphs, useful to capture the “asymptotic” behavior of the algorithms, we also developed experiments by considering a widely used graph from the real world, i.e., the Internet graph. © 1998, ACM. All rights reserved.

关键词： dynamic algorithms experimental analysis of algorithms shortest paths

来源：评论

学校读者我要写书评

暂无评论

Semidynamic algorithms for maintaining single-source shortest path trees

引用

ALGORITHMICA 1998年第3期22卷 250-274页

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Matemat Pura & Appl I-67010 Coppito AQ Italy Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We consider the problem of updating a single-source shortest path tree in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph;they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log rr) amortized time per vertex update: where a vertex is considered updated ii it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O(root mlog n) amortized time perverter update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6]. require simple datastructures that are really suitable for a practical and straightforward implementation.

关键词： single-source shortest path dynamic algorithms amortized complexity output complexity

来源：评论

学校读者我要写书评

暂无评论

On certificates and lookahead in dynamic graph problems

引用

ALGORITHMICA 1998年第4期21卷 377-394页

作者： Khanna, S Motwani, R Wilson, RH AT&T Bell Labs Dept Fundamental Math Res Murray Hill NJ 07974 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Sandia Natl Labs Intelligent Syst & Robot Ctr Albuquerque NM 87185 USA

Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of fundamental directed graph problems like strong connectivity and transitive closure, as well as some undirected graph problems such as maximum matchings and cuts. We provide some explanation for this lack of success by presenting quadratic lower bounds on the certificate complexity of the seemingly difficult problems, in contrast to the known linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems, a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that lookahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic algorithms for strong connectivity and transitive closure.

关键词： dynamic algorithms graph algorithms lookahead algorithms graph certificates sparsification strong connectivity transitive closure

来源：评论

学校读者我要写书评

暂无评论

Dog bites postman: Point location in the moving Voronoi diagram and related problems

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1998年第3期8卷 321-342页

作者： Devillers, O Golin, MJ INRIA F-06902 Sophia Antipolis France Hong Kong Univ Sci & Technol Kowloon Hong Kong

In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the question: given a point q(0) and time t(0) who is the nearest postman to q(0) at time t(0)? We present a randomized incremental data structure that answers the query in expected O(log(2) n) time. The second variation views a query point as a dog searching for a postman to bite and finds the postman that a dog running with speed v(d) could reach first. While it is quite straightforward to design a data structure for the first problem, designing one for the second appears more difficult. We show that if the dog is quicker than all of the postmen then there is a nice correspondence between the problems. This correspondence will permit us to use the data structure developed for the first problem to solve the second one in O(log(2) n) time as well. The proposed structure is semi-dynamic, that is the set of postmen can be modified by inserting new postmen. A fully dynamic structure that also supports deletions can be obtained, but in that case the query time becomes O(log(3) n).

关键词： computational geometry moving points Voronoi Delaunay randomized algorithms dynamic algorithms localisation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：