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

Arboricity, h-index, and dynamic algorithms

THEORETICAL COMPUTER SCIENCE 2012年 426卷 75-90页

作者： Lin, Min Chih Soulignac, Francisco. J. Szwarcfiter, Jayme L. Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Inst Calculo Buenos Aires DF Argentina Univ Fed Rio de Janeiro Inst Matemat NCE BR-20001970 Rio De Janeiro RJ Brazil COPPE BR-20001970 Rio De Janeiro RJ Brazil

We propose a new data structure for manipulating graphs, called h-graph, which is particularly suited for designing dynamic algorithms. The structure itself is simple, consisting basically of a triple of elements, for each vertex of the graph. The overall size of all triples is O(n + m), for a graph with n vertices and m edges. We describe algorithms for performing the basic operations related to dynamic applications, as insertions and deletions of vertices or edges, and adjacency queries. The data structure employs a technique first described by Chiba and Nishizeki [Chiba, Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1) (1985) 210-223], and relies on the arboricity of graphs. Using the proposed data structure, we describe several dynamic algorithms for solving problems as listing the cliques of a given size, recognizing diamond-free graphs, and finding simple, simplicial and dominated vertices. These algorithms are the first of their kind to be proposed in the literature. In fact, the dynamic algorithms for the above problems lead directly to new static algorithms, and using the data structure we also design new static algorithms for the problems of counting subgraphs of size 4, recognizing cop-win graphs and recognizing strongly chordal graphs. The complexities of all of the proposed static algorithms improve over the complexities of the so far existing algorithms, for graphs of low arboricity. In addition, for the problems of counting subgraphs of size 4 and recognizing diamond-free graphs, the improvement is general. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Arboricity Cop-win graphs Data structures Diamond-free graphs dynamic algorithms h-index Strongly chordal graphs

来源：评论

学校读者我要写书评

暂无评论

Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence

引用

ALGORITHMICA 2002年第2期33卷 168-182页

作者： Korupolu, MR Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms, which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph, We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for edge connectivity and O(log n) amortized time per operation for cycle equivalence, The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log(3)n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem.

关键词： dynamic algorithms graph algorithms cycle equivalence connected graphs edge and vertex connectivity randomized algorithms compiler optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Partially dynamic algorithms for Distributed Shortest Paths and their Experimental Evaluation

引用

JOURNAL OF COMPUTERS 2007年第9期2卷 16-26页

作者： Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Petricola, Alberto Univ Aquila Dipartimento Ingn Elettr & Informaz I-67040 Laquila Italy

In this paper, we study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite). In this paper we propose a partially dynamic algorithm that overcomes most of these limitations. In particular, it is able to concurrently update shortest paths and in many cases its convergence is quite fast. These properties are highlighted by an experimental study whose aim is to show the effectiveness of the proposed algorithms also in the practical case.

关键词： Distributed networks dynamic algorithms shortest paths routing experimental evaluation network simulation environment

来源：评论

学校读者我要写书评

暂无评论

ON dynamic algorithms FOR FACTORIZATION INVARIANTS IN NUMERICAL MONOIDS

引用

MATHEMATICS OF COMPUTATION 2017年第307期86卷 2429-2447页

作者： Barron, Thomas O'Neill, Christopher Pelayo, Roberto Univ Kentucky Dept Math Lexington KY 40506 USA Texas A&M Univ Dept Math College Stn TX 77843 USA Univ Calif Davis Dept Math One Shields Ave Davis CA 95616 USA Univ Hawaii Dept Math Hilo HI 96720 USA

Studying the factorization theory of numerical monoids relies on understanding several important factorization invariants, including length sets, delta sets, and w-primality. While progress in this field has been accelerated by the use of computer algebra systems, many existing algorithms are computationally infeasible for numerical monoids with several irreducible elements. In this paper, we present dynamic algorithms for the factorization set, length set, delta set, and w-primality in numerical monoids and demonstrate that these algorithms give significant improvements in runtime and memory usage. In describing our dynamic approach to computing w-primality, we extend the usual definition of this invariant to the quotient group of the monoid and show that several useful results naturally extend to this broader setting.

关键词： Monoid computer use factorization dynamic algorithms Quotient group dynamic algorithms Runtime Invariant

来源：评论

学校读者我要写书评

暂无评论

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2014年第2期47卷 240-247页

作者： Chan, Timothy M. Pathak, Vinayak Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

At SODA'1 0, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + root 3)/2 + epsilon approximate to 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + root 2)/2 approximate to 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Streaming algorithms dynamic algorithms High dimension

来源：评论

学校读者我要写书评

暂无评论

Online and dynamic algorithms for Set Cover 2017

Online and Dynamic Algorithms for Set Cover

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Gupta, Anupam Krishnaswamy, Ravishankar Kumar, Amit Panigrahi, Debmalya Carnegie Mellon Univ Pittsburgh PA 15213 USA Microsoft Res Bengaluru India IIT Delhi New Delhi India Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450345286

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offine algorithms for set cover. The former leads to a competitive ratio of O(log n(t)), where n(t) is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on f(t), the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

关键词： Set cover recourse dynamic algorithms competitive ratio online algorithms vertex cover graph matching hypergraph matching

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic algorithms for Euclidean Steiner Tree 1

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Chan, T-H Hubert Goranci, Gramoz Jiang, Shaofeng H-C Wang, Bo Xue, Quan Univ Hong Kong Hong Kong Peoples R China Univ Vienna Vienna Austria Peking Univ Beijing Peoples R China

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of terminal points X in R-d, possibly using points not in X which are called Steiner points. Even though near-linear time (1+ epsilon)-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a (1+epsilon)-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time O(poly log n) with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP sub-problems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries.

关键词： Steiner Tree dynamic algorithms Approximation Schemes

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic algorithms for Longest Increasing Subsequence 2021

Improved Dynamic Algorithms for Longest Increasing Subsequen...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Kociumaka, Tomasz Seddighin, Saeed Univ Calif Berkeley Berkeley CA 94720 USA Toyota Technol Inst Chicago Chicago IL USA

ISBN: (纸本)9781450380539

We study dynamic algorithms for the longest increasing subsequence (LIS) problem. A dynamic LIS algorithm maintains a sequence subject to operations of the following form arriving one by one: insert an element, delete an element, or substitute an element for another. After each update, the algorithm must report the length of the longest increasing subsequence of the current sequence. Our main contribution is the first exact dynamic LIS algorithm with sublinear update time. More precisely, we present a randomized algorithm that performs each operation in time (O) over tilde (n(4/5)) and, after each update, reports the answer to the LIS problem correctly with high probability. We use several novel techniques and observations for this algorithm that may find applications in future work. In the second part of the paper, we study approximate dynamic LIS algorithms, which are allowed to underestimate the solution size within a bounded multiplicative factor. In this setting, we give a deterministic (1 - o(1))-approximation algorithm with update time O(n(o(1))). This result improves upon the previous work of Mitzenmacher and Seddighin (STOC'20) that provides an Omega(epsilon(O(1/epsilon)))-approximation algorithm with update time (O) over tilde (n(epsilon)) for any epsilon > 0.

关键词： Longest Increasing Subsequence dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster and dynamic algorithms For Maximal End-Component Decomposition And Related Graph Problems In Probabilistic Verification 11

Faster and Dynamic Algorithms For Maximal End-Component Deco...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Krishnendu Chatterjee Monika Henzinger Institute of Science and Technology Austria Fakultat fur Informatik Universitat Wien

ISBN: (纸本)9780898719932

We present faster and dynamic algorithms for the following problems arising in probabilistic verification: Computation of the maximal end-component (mec) decomposition of Markov decision processes (MDPs), and of the almost sure winning set for reachability and parity objectives in MDPs. We achieve the following running time for static algorithms in MDPs with graphs of n vertices and m edges: (1) O(m · min{m~(1/2), n~(2/3)}) for the mec decomposition, improving the longstanding O(m·n) bound; (2) O(m·n~(2/3)) for reachability objectives, improving the previous O(m · m~(1/2)) bound for m > n~(4/3); and (3) O(m · min{ m~(1/2), n~(2/3) } · log(d)) for parity objectives with d priorities, improving the previous O(m · m~(1/2) · d) bound. We also give incremental and decremental algorithms in linear time for mec decomposition and reachability objectives and O(m· log d) time for parity objectives.

关键词： Probabilistic verification Parity objectives Graph decomposition dynamic graph algorithms Maximal end-components dynamic algorithms Markov chain Accessibility Probability Parity Fasting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：