2 papers
cs.DS2026
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
cs.DS2025
Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein
We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph : a small collect…