A Note on Dynamic Bidirected Dyck-Reachability with Cycles

2024/01/07 by Qirun Zhang, Zhang, Qirun
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Programming Languages (cs.PL)

paper · pdf · doi:10.48550/arxiv.2401.03570

openalex publication_date 2024/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recently, Li et al. [2022] presented a dynamic Dyck-reachability algorithm for bidirected graphs. The basic idea is based on updating edge weights in a data structure called the merged graph G_m. As noted in Krishna et al. [2023], the edge deletion procedure described in the algorithm of Li et al. [2022] cannot properly update the weights in the presence of cycles in G_m. This note discusses the cycle case and the time complexity.

Related

• Dynamic Complexity of the Dyck Reachability
• Dynamic Meta-theorems for Distance and Matching
• Dynamic complexity of Reachability: How many changes can we handle?
• Reachability and Distances under Multiple Changes
• The Decidability and Complexity of Interleaved Bidirected Dyck Reachability