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

Sparsification - A technique for speeding up dynamic graph algorithms

JOURNAL OF THE ACM 1997年第5期44卷 669-696页

作者： Eppstein, D Galil, Z Italiano, GF Nissenzweig, A Univ Calif Irvine Dept Informat & Comp Sci Irvine CA 92717 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Ca Foscari Venezia Dipartimento Matemat Applicata & Informat Venice Italy Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

We provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in time O(n(1/2)) per change;3-edge connectivity, in time O(n(2/3)) per change;4-edge connectivity, in time O(ncr(n)) per change;k-edge connectivity for constant k, in time O(nlogn) per change;2-vertex connectivity, and 3-vertex connectivity, in time O(n) per change;and 4-vertex connectivity, in time O(n alpha(n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call sparsification.

关键词： dynamic graph algorithms minimum spanning trees edge and vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

Meerkat: A Framework for dynamic graph algorithms on GPUs

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2024年第5-6期52卷 400-453页

作者： Concessao, Kevin Jude Cheramangalath, Unnikrishnan Dev, Ricky Nasre, Rupesh Indian Inst Technol Palakkad Dept Comp Sci & Engn Palakkad India Indian Inst Technol Madras Dept Comp Sci & Engn Chennai India

graph algorithms are challenging to implement due to their varying topology and irregular access patterns. Real-world graphs are dynamic in nature and routinely undergo edge and vertex additions, as well as, deletions. Typical examples of dynamic graphs are social networks, collaboration networks, and road networks. Applying static algorithms repeatedly on dynamic graphs is inefficient. Further, due to the rapid growth of unstructured and semi-structured data, graph algorithms demand efficient parallel processing. Unfortunately, we know only a little about how to efficiently process dynamic graphs on massively parallel architectures such as GPUs. Existing approaches to represent and process dynamic graphs are either not general or are inefficient. In this work, we propose a graph library for dynamic graph algorithms over a GPU-tailored graph representation and exploits the warp-cooperative work-sharing execution model. The library, named Meerkat, builds upon a recently proposed dynamic graph representation on GPUs. This representation exploits a hashtable-based mechanism to store a vertex's neighborhood. Meerkat also enables fast iteration through a group of vertices, a pattern common and crucial for achieving performance in graph applications. Our framework supports dynamic edge additions and edge deletions, along with their batched versions. Based on the efficient iterative patterns encoded in Meerkat, we implement dynamic versions of popular graph algorithms such as breadth-first search, single-source shortest paths, triangle counting, PageRank, and weakly connected components. We evaluated our implementations over the ones in other publicly available dynamic graph data structures and frameworks: GPMA, Hornet, and faimgraph. Using a variety of real-world graphs, we observe that Meerkat significantly improves the efficiency of the underlying dynamic graph algorithm, outperforming these frameworks.

关键词： dynamic graph algorithms GPU programming Parallel computing CUDA

来源：评论

学校读者我要写书评

暂无评论

Randomized fully dynamic graph algorithms with polylogarithmic time per operation

引用

JOURNAL OF THE ACM 1999年第4期46卷 502-516页

作者： Henzinger, MR King, V Google Inc Mountain View CA 94043 USA Univ Victoria Dept Comp Sci Victoria BC Canada

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of Omega(m(0)) operations, where m(0) is the number of edges in the initial graph, the expected time for p updates is O(p log(3) n) (Throughout the paper the logarithms are base 2.) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem ("Does the removal of k given edges disconnect the graph?") the expected time for p updates is O(p log(3) n) and the expected time for q queries is O(qk log(3) n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log(3) n). This implies an algorithm to maintain a 1 + epsilon-approximation of the minimum spanning tree in expected time O((p log(3)n log U)/epsilon) for p updates, where the weights of the edges are between 1 and U.

关键词： connectivity dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of algorithms with Predictions for dynamic graph Problems 15

On the Complexity of Algorithms with Predictions for Dynamic...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Henzinger, Monika Saha, Barna Seybold, Martin P. Ye, Christopher Inst Sci & Technol Austria ISTA Klosterneuburg Austria Univ Calif San Diego La Jolla CA 92093 USA Univ Vienna Vienna Austria

ISBN: (纸本)9783959773096

algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) 6-accurate predictions where each predicted request matches the true request with probability S, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and 6-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by *** et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.

关键词： dynamic graph algorithms algorithms with Predictions

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for Approximate Steiner Trees

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2025年第6-8期37卷

作者： Raikwar, Hemraj Sadharakiya, Harshil Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati India

This study investigates the dynamic Steiner tree problem. The objective of the Steiner tree problem is to compute a minimum-weight tree connecting a set of designated vertices called terminals in a connected weighted graph with positive real edge weights. A dynamic graph is one in which the set of edges, the set of vertices, or both can change over time. Here, we focus on dynamic graphs where edges can change over time. The work begins by establishing a lower bound on the update time required to maintain an MST heuristic based (2-& varepsilon;)$$ \left(2-\epsilon \right) $$-approximate Steiner tree (where & varepsilon;$$ \epsilon $$ is a small fraction) in a general graph undergoing edge insertions or deletions. Subsequently, we propose two dynamic algorithms: A fully dynamic algorithm to maintain an approximate Steiner tree in planar graphs and an incremental algorithm to maintain an approximate Steiner tree in general graphs. We focus on edge-weighted connected graphs. The graph undergoes dynamic updates where edges with specific weights can be either inserted or deleted. The goal is to efficiently compute a Steiner tree of the updated graph, guaranteeing a solution quality (Steiner tree cost) within a good factor of the optimal Steiner tree. In the fully dynamic case, our analysis demonstrates that the presented algorithm maintains an approximation factor of (2+& varepsilon;)$$ \left(2+\epsilon \right) $$. The worst case update time for processing a series of k$$ k $$ number of updates is & Otilde;(|S|2n+|S|D+n)$$ \overset{\widetilde }{O}\left({\left|S\right|}<^>2\sqrt{n}+|S|D+n\right) $$ where n$$ n $$ is the cardinality of the vertex set of the input graph, D$$ D $$ denotes the unweighted diameter of the updated graph, and k is an element of Z+:1 <= k <=(n+m)$$ k\in {Z}<^>{+}:1\le k\le \left(\sqrt{n+m}\right) $$. It is shown that the update time can be improved to O(n(& varepsilon;')-2)$$ O\left(n{\left({\epsilon}<^>{\prime}\right)}<^>{-2}\right) $$ in a specia

关键词： approximation algorithms dynamic distance oracle dynamic graph algorithms fully dynamic algorithm shortest path forest Steiner tree

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Simple Greedy Algorithm for dynamic graph Orientation

引用

ALGORITHMICA 2020年第2期82卷 245-259页

作者： Berglin, Edvin Brodal, Gerth Stolting Aarhus Univ Aarhus Denmark

graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs allow for insertion and deletion of edges, one may have to flip the orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as our sparsity measure. With an immensely simple greedy algorithm, we get parametrized trade-off bounds between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in Ologn flips) for almost all values of arboricity and beat it for either constant or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O1 and Ologn flips nearly matching out-degree bounds to their respective amortized solutions.

关键词： dynamic graph algorithms graph arboricity Edge orientations

来源：评论

学校读者我要写书评

暂无评论

A Simple Greedy Algorithm for dynamic graph Orientation 28

A Simple Greedy Algorithm for Dynamic Graph Orientation

引用

28th International Symposium on algorithms and Computation (ISAAC)

作者： Berglin, Edvin Brodal, Gerth Stolting Aarhus Univ Aarhus Denmark

ISBN: (纸本)9783959770545

关键词： dynamic graph algorithms graph arboricity Edge orientations

来源：评论

学校读者我要写书评

暂无评论

Parallel Batch-dynamic graph Connectivity 19

Parallel Batch-Dynamic Graph Connectivity

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Acar, Umut A. Anderson, Daniel Blelloch, Guy E. Dhulipala, Laxman Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450361842

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(1g(2) n) amortized time per edge insertion or deletion, and O(1g n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where A is the average batch size of all deletions, our algorithm achieves O(1g n lg(1 + n/A)) expected amortized work per edge insertion and deletion and O (1g(3) n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k lg(1 + n/ k)) expected work and O(1g n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.

关键词： parallel graph algorithms graph connectivity dynamic graph algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

An Invitation to dynamic graph Problems: Lower Bounds - III

引用

RESONANCE-JOURNAL OF SCIENCE EDUCATION 2022年第10期27卷 1777-1787页

作者： Kashyop, Manas Jyoti Narayanaswamy, N. S. Inst Math Sci Chennai Tamil Nadu India IIT Madras Dept CSE Chennai Tamil Nadu India

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part(1) of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part(2) of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds.

关键词： dynamic graph algorithms adversary cell-probe lower bounds conditional lower bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：