Morse, Gregory, Kozsik, Tamás (2026) Fully dynamic strong connectivity and reachability in digraphs Annales Mathematicae et Informaticae. 63. pp. 88-106.
![[thumbnail of 88_106.pdf]](http://publikacio.uni-eszterhazy.hu/style/images/fileicons/text.png) |
pdf
88_106.pdf Download (740kB) [error in script] |
Absztrakt (kivonat)
Computing strongly connected components (SCCs) and reachability in directed graphs is fundamental in compilers, static analysis, and many graph algorithms. While efficient offline algorithms are well known, maintaining this information dynamically under both edge insertions and deletions remains challenging. This paper presents a deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs. The approach combines a union–find structure for efficient merging of SCCs during edge insertions with localized recomputation of SCCs using Nuutila’s algorithm when deletions potentially split a component. Reachability information is maintained at the SCC level and propagated through the condensation DAG. For a current graph with n vertices and m edges, the resulting algorithm supports O(1) reachability queries while updates have worst-case complexity O(m+n2) due to reachability propagation. Although this does not improve the best known theoretical bounds for specialized dynamic algorithms, the method is simple, deterministic, and well suited to sparse graphs such as control flow graphs (CFGs). Experimental evaluation on random graphs and real program CFGs shows that the algorithm significantly outperforms repeated offline recomputation in practical scenarios.
| Mű típusa: | Folyóiratcikk - Journal article |
|---|---|
| Szerző: | Szerző neve Email MTMT azonosító ORCID azonosító Közreműködés Morse, Gregory NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző Kozsik, Tamás NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző |
| Megjegyzés: | The research has been supported by the European Union, co-financed by the European Social Fund (EFOP-3.6.2-16-2017-00013, Thematic Fundamental Research Collaborations Grounding Innovation in Informatics and Infocommunications). |
| Kapcsolódó URL-ek: | |
| Kulcsszavak: | fully dynamic algorithm, strongly connected components, reachability, directed graphs, incremental algorithm, decremental algorithm, graph maintenance |
| Nyelv: | angol |
| Kötetszám: | 63. |
| DOI azonosító: | 10.33039/ami.2026.06.002 |
| Felhasználó: | Tibor Gál |
| Dátum: | 20 Júl 2026 07:23 |
| Utolsó módosítás: | 20 Júl 2026 07:23 |
| URI: | http://publikacio.uni-eszterhazy.hu/id/eprint/9297 |
 |
Tétel nézet |
