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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Super-Logarithmic Lower Bounds for dynamic graph Problems 64

Super-Logarithmic Lower Bounds for Dynamic Graph Problems

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Larsen, Kasper Green Yu, Huacheng Aarhus Univ Aarhus Denmark Princeton Univ Princeton NJ USA

ISBN: (纸本)9798350318944

In this work, we prove a (Omega) over tilde (lg(3/2) n) unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

关键词： cell-probe model data structure lower bounds dynamic reachability dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Trade-Offs in dynamic Coloring for Bipartite and General graphs

引用

ALGORITHMICA 2023年第4期85卷 854-878页

作者： Kashyop, Manas Jyoti Narayanaswamy, N. S. Nasre, Meghana Potluri, Sai Mohith Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India

The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using Delta + 1 or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS'17, and Solomon and Wein in ESA'18. In SODA'18, Bhattacharya et al. presented a randomized algorithm that uses Delta + 1 colors and achieves amortized O (log Omega) update time. In STACS'20, Henzinger and Peng presented a randomized (Delta + 1)-coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized (Delta + 1)-coloring algorithm with amortized O(1) update time. While works of Bhattacharya et al., and Henzinger and Peng are very efficient in terms of update time, they do not address the number of recolorings per update. We bridge this gap by providing efficient update time algorithms with constant number of recolorings. Moreover our algorithm is deterministic as opposed to the works of Bhattacharya et al. in SODA'18, and Henzinger and Peng in STACS'20. Next, we study bipartite graphs which can be optimally colored in the static setting. We show that even in the incremental setting (where edges are added to the graph and no edge can be deleted), there is a bad update sequence which forces the update time to be at least Omega(logn) in the amortized setting and Omega(n) in the worst case. This possibly explains the lack of any results on dynamic coloring specific to bipartite graphs. We circumvent this lower bound by proposing two approaches. Firstly, we allow the use of more than two colors and obtain significantly better update time. Second, we introduce the idea of implicit coloring. If the color of a vertex is explicitly stored in a data structure and updated at end of every update then we call such an algorithm as explicit coloring

关键词： dynamic graph algorithms graph coloring

来源：评论

学校读者我要写书评

暂无评论

A dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications 2024

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Spar...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Kyng, Rasmus Meierhans, Simon Gutenberg, Maximilian Probst Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9798400703836

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results: the first data structure to maintain m(o(1))-approximate all-pairs shortest paths (APSP) in an m-edge graph undergoing edge insertions and deletions with worst-case update time m(o(1)) and query time (O) over tilde (1), and a data structure to maintain a tree T that has diameter no larger than a subpolynomial factor than the underlying graph G that is undergoing edge insertions and deletions where each update is handled in amortized subpolynomial time, and a simpler and more efficient data structure to maintain a (1+epsilon)-approximate single-source shortest paths (SSSP) tree T in a graph undergoing edge deletions in amortized time m(o(1)) per update. All our data structures are deterministic. For the last two data structures, we further have that while the trees T are not subgraphs of G, they do embed with small edge congestion into G. This is in stark contrast to previous approaches and is particularly useful for algorithms that use these data structures internally to route flow along shortest paths. To illustrate the power of our new toolbox, we show that our SSSP data structure can be used directly to give a deterministic implementation of the classic MWU algorithm for approximate undirected minimum-cost flow running in time m(1+o(1)). Previously, Bernstein-Gutenberg-Saranurak [FOCS21] had built a randomized data structure achieving m(1+o(1)) time whp. By using our SSSP data structure in the recent almost-linear time algorithm for computing Gomory-Hu trees by Abboud-Li-Panigrahi-Saranurak [FOCS23], we simplify their algorithm significantly and slightly improve their runtime. To obtain our toolbox, we give the first algorithm that, given a graph G undergoing edge insertions and deletions and a dynamic terminal set A, maintains a vertex sparsif

关键词： Shortest-Paths dynamic graph algorithms All-Pair Shortest-Paths

来源：评论

学校读者我要写书评

暂无评论

Single-source shortest paths and strong connectivity in dynamic planar graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 97-111页

作者： Charalampopoulos, Panagiotis Karczmarz, Adam Univ Warsaw Inst Informat Warsaw Poland Kings Coll London Dept Informat London England Efi Arazi Sch Comp Sci Interdisciplinary Ctr Herzliya Herzliyya Israel

We give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with (O) over tilde (n(4/5)) worst-case update time and O(log(2) n) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. We then extend our approach, obtaining a data structure that can maintain a planar digraph under edge insertions and deletions, and is capable of returning the identifier of the strongly connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for an important class of digraphs. (C) 2021 Elsevier Inc. All rights reserved.

关键词： dynamic graph algorithms Planar graphs Single-source shortest paths Strong connectivity

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for dynamic Bidirected Dyck-Reachability

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2022年第POPL期6卷 1–29页

作者： Li, Yuanbo Satya, Kris Zhang, Qirun Georgia Inst Technol Atlanta GA 30332 USA

Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on bidirected graphs where each edge mu -> (li) upsilon labeled by an open parenthesis "(sic)(i)" is accompanied with an inverse edge v (sic) u labeled by the corresponding close parenthesis "(sic)(i)", and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with.. nodes and.. edges, the optimal bidirected Dyck-reachability algorithm computes all-pairs reachability information in O(m) time. This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires O(n(2)) update time to achieve O(1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees. Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update (i.e., edge insertion and deletion) in O(n . alpha(n)) time and support any all-pairs reachability query in O(1) time, where alpha(n) is the inverse Ackermann function. We have

关键词： dynamic graph algorithms Dyck-Reachability Bidirected graphs Incremental Analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：