Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Notes on the Linear Algebraic View of Regularity Lemmas
Greg Bodwin, Tuong Le
When regularity lemmas were first developed in the 1970s, they were described as results that promise a partition of any graph into a ``small'' number of parts, such that the graph…
cs.DS2024
Improved Online Reachability Preservers
Greg Bodwin, Tuong Le
A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an -node directed input graph among a set of given demand pairs $P…