Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni, Nikos Parotsidis · 2025
Read Fully Dynamic Algorithms for Transitive Reduction by Gramoz Goranci, Adam Karczmarz, Ali Momeni, Nikos Parotsidis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18161.txt.
Description
Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis built the first full dynamic tools for transitive reduction. Their paper, from twenty twenty-five, deals with directed graphs. A transitive reduction is the smallest subgraph that keeps the reach facts between all pairs of points. Graphs in real use change edge by edge, so the reduction must keep up. Past work lagged in that live setting.
Their first tool updates in near best time for sparse graphs. It can even take in bursts of edges at one point, or cut sets of edges at once. A second tool leans on fast matrix math for dense cases. Readers in algorithms get live upkeep of a base graph form.
Catalog record
| CREATOR | Gramoz Goranci, Adam Karczmarz, Ali Momeni, Nikos Parotsidis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 143 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18161