Constant-time Connectivity and 2-Edge Connectivity Querying in Dynamic Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917220514267136 |
|---|---|
| author | Xu, Lantian Zhang, Junhua Wen, Dong Qin, Lu Zhang, Ying Lin, Xuemin |
| author_facet | Xu, Lantian Zhang, Junhua Wen, Dong Qin, Lu Zhang, Ying Lin, Xuemin |
| contents | Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. In addition, we extend our connectivity maintenance algorithms to maintain 2-edge connectivity. Our performance studies on real large datasets show considerable improvement of our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17285 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Constant-time Connectivity and 2-Edge Connectivity Querying in Dynamic Graphs Xu, Lantian Zhang, Junhua Wen, Dong Qin, Lu Zhang, Ying Lin, Xuemin Databases Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. In addition, we extend our connectivity maintenance algorithms to maintain 2-edge connectivity. Our performance studies on real large datasets show considerable improvement of our algorithms. |
| title | Constant-time Connectivity and 2-Edge Connectivity Querying in Dynamic Graphs |
| topic | Databases |
| url | https://arxiv.org/abs/2601.17285 |