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

THEORETICAL COMPUTER SCIENCE 1998年第1-2期201卷 249-262页

作者： Ferragina, P Grossi, R Montangero, M Univ Florence Dipartimento Sistemi & Informat I-50121 Florence Italy Univ Pisa Dipartimento Informat I-56100 Pisa Italy Univ Salerno Dipartimento Informat & Applicaz R Capocelli I-84100 Salerno Italy

We investigate the problem of maintaining the are labels in the suffix tree data structure (Gusfield et al., 1992;Amir et al., 1994) when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds (Fiala and Green, 1989;Larson, 1996) or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to the global rebuilding technique in Overmars, 1983). Unfortunately, the former approach is simple and space efficient at the cost of attaining amortized bounds for the single update;the latter is space consuming, in practice, because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple realtime algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs. (C) 1998 - Elsevier Science B.V. All rights reserved.

关键词： data compression dynamic data structure string processing text indexing

来源：评论

学校读者我要写书评

暂无评论

Maintaining the classes of 4-edge-connectivity in a graph on-line

引用

ALGORITHMICA 1998年第3期20卷 242-276页

作者： Dinitz, Y Westbrook, J Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.

关键词： dynamic algorithm dynamic data structure graph algorithm edge-connectivity connectivity class component analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Rounding arrangements dynamically

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1998年第2期8卷 157-178页

作者： Guibas, LJ Marimont, DH Stanford Univ Dept Comp Sci Stanford CA 94305 USA Xerox Corp Palo Alto Res Ctr Palo Alto CA 94304 USA

We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene(7) and Hobby,(11) it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,(16) it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments,, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley's dynamic algorithm in a way that preserves the desirable properties of each.

关键词： arrangement vertical trapezoidal decomposition dynamic data structure randomized algorithm robustness rounding

来源：评论

学校读者我要写书评

暂无评论

An improved dynamically allocated data structure scheme for power system problems

引用

International Journal of Modelling & Simulation 1997年第2期17卷 61-61页

作者： Yehia, M. Chedid, R. Jaber, Z. Ilic, M. American University of Beirut New York NY 10022 850 Third Ave. Lebanon Massachusetts Inst. of Technology Cambridge MA 02139 77 Mass. Ave. United States

This paper proposes two new dynamically allocated data structures for large and sparse matrices occurring in electric power system problems. The proposed data structures have the features of optimizing memory requirement and fast accessing of data. Their advantages as compared to classical methods will be discussed, and a tradeoff analysis between memory requirement and accessing time will be performed. It will be shown that improvement in both memory requirement and processing time can be achieved.

关键词： dynamic data structure Electric power systems Sparse matrices

来源：评论

学校读者我要写书评

暂无评论

On-line maintenance of triconnected components with SPQR-trees

引用

ALGORITHMICA 1996年第4期15卷 302-318页

作者： DiBattista, G Tamassia, R UNIV ROMA LA SAPIENZA DIPARTIMENTO INFORMAT & SISTEMIST I-00185 ROME ITALY BROWN UNIV DEPT COMP SCI PROVIDENCE RI 02912 USA

We consider the problem of maintaining on-line the triconnected components of a graph G. Let n be the current number of vertices of G. We present an O (rt)-space data structure that supports insertions of vertices and edges, and queries of the type ''Are there three vertex-disjoint paths between vertices v(1) and v(2)?'' A sequence of k operations takes time O(k . alpha(k,n)) if G is biconnected (alpha(k,n) denotes the well-known Ackermann's function inverse), and time O(n log n + k) if G is not biconnected. Note that the bounds do not depend on the number of edges of G. We use the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.

关键词： vertex connectivity dynamic algorithm dynamic data structure graph decomposition triconnected components network reliability

来源：评论

学校读者我要写书评

暂无评论

NEW RESULTS ON dynamic PLANAR POINT LOCATION

引用

SIAM JOURNAL ON COMPUTING 1992年第5期21卷 972-999页

作者： SIU, WC JANARDAN, R UNIV MINNESOTA DEPT COMP SCIMINNEAPOLISMN 55455

A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses O(n) space, has a worst-case query time of O(log2 n), and a worst-case update time of O(log n), where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n + k)) (respectively, O(k log n)) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of tine segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log2 n log log n + k) time (or O(log n log log n + k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.

关键词： COMPUTATIONAL GEOMETRY dynamic data structure PLANAR SUBDIVISION POINT LOCATION PRIORITY SEARCH TREES TREES OF BOUNDED BALANCE

来源：评论

学校读者我要写书评

暂无评论

DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1992年第3期2卷 311-333页

作者： Chiang, Yi-Jen Tamassia, Roberto Brown Univ Dept Comp Sci Providence RI 02912 USA

We present a fully dynamic data structure for point location in a monotone subdivision, based on the trapezoid method. The operations supported are insertion and deletion of vertices and edges, and horizontal translation of vertices. Let n be the current number of vertices of the subdivision. Point location queries take O (log n) time, while updates take O (log(2) n) time (amortized for vertex insertion/deletion and worst-case for the other updates). The space requirement is O(n log n). This is the first fully dynamic point location data structure for monotone subdivisions that achieves optimal query time.

关键词： Computational geometry planar point location dynamic data structure monotone subdivision analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

AN INCREMENTAL RECONSTRUCTION METHOD FOR dynamic PLANAR POINT LOCATION

引用

INFORMATION PROCESSING LETTERS 1991年第2期37卷 79-83页

作者： TAMASSIA, R UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

We present a fully dynamic technique for point location in triangulations that allows a tradeoff between query and update time, and can be used in conjunction with any of the known static point location data structures. Let S be a triangulation whose current number of vertices is n. We show that for any smooth nondecreasing integer function b(n) with 2 less-than-or-equal-to b(n) less-than-or-equal-to square-root-n, there exists a dynamic point location data structure for S with space O(n), query time O(log2n)/log b(n)), and update time O((log2n)b(n)/log b(n).

关键词： POINT LOCATION PLANAR SUBDIVISION TRIANGULATION dynamic data structure ONLINE ALGORITHM COMPUTATIONAL GEOMETRY ANALYSIS OF ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

dynamic MAINTENANCE OF PLANAR DIGRAPHS, WITH APPLICATIONS

引用

ALGORITHMICA 1990年第4期5卷 509-527页

作者： TAMASSIA, R PREPARATA, FP UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

We show that a planarst-graphG admits two total orders on the setV∪E ∪F, whereV, E, andF are respectively the set of vertices, edges, and faces ofG, with |V| =n. Assuming thatG is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit anO(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in timeO(logn). The discovered structural properties of planarst-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planarst-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.

关键词： Planarst-graph Transitive closure Point location Contact-chain Planar subdivision dynamic data structure On-line algorithm

来源：评论

学校读者我要写书评

暂无评论

A PRACTICAL METHOD FOR COMPRESSING SPARSE MATRICES WITH VARIANT ENTRIES

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1990年第3-4期36卷 163-173页

作者： AOE, J Department of Information Science and Intelligent Systems The University of Tokushima Minami-Josanjima-Cho Tokushima-Shi 770 Japan

A row displacement method compresses efficiently a sparse matrix into a one-dimensional array. The access time with this method isO(l), but the application was restricted to the static matrices. In order to extend the use of the row displacement method to the dynamic matrices, the algorithms for insertion and deletion are proposed and the effectivity is confirmed by theoretical and empirical observations.

关键词： A large sparse matrix dynamic data structure fast access storing and searching table compression table look up E.1 F.2.2 H.3.3

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：