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

CREATORGramoz Goranci, Adam Karczmarz, Ali Momeni, Nikos Parotsidis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE143 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18161

Browse the full library · About the Tower of Babel