Efficient Algorithms for Dynamic Bidirected Dyck-Reachability
summary
Presents a dynamic algorithm that maintains all-pairs bidirected Dyck-reachability with O(n α(n)) update time per edge and O(1) queries, using a merged-graph representation that collapses Dyck-equivalent nodes and splits them precisely on deletions to avoid redundant work. Implements the algorithm for Java alias and context-sensitive data-dependence analyses and evaluates against recomputing static Dyck and an incremental Datalog solver, reporting roughly tenfold speedup over the incremental solver and orders of magnitude speedup over naïve recomputation; artifacts available.
AI-written summary · about
chapters (7)
- 0:00Start
- 1:09An Incremental Alias Analysis Example
- 4:58Approach
- 7:07Challenge
- 12:05Complexity
- 12:35Evaluation
- 17:04Conclusion
related talks
53mData Deduplication For Redundant Graph Structures Files
21mMutual Refinements of Context-Free Language Reachability
17mExploiting the Sparseness of Control-Flow and Call Graphs for Efficient and On-...
28mReasoning about Distributed Reconfigurable Systems
01h 09mPlenary: Neighborhoods Banding Together: Reasoning Globally about Programs
18mOn the Verification of a Subgraph Construction Algorithm
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
40mUtilizing Structure in Combinatorial Solving and Reasoning