3 papers
cs.DS2025
Low Recourse Arborescence Forests Under Uniformly Random Arcs
J Niklas Dahlmeier, D Ellis Hershkowitz
In this work, we study how to maintain a forest of arborescences of maximum arc cardinality under arc insertions while minimizing recourse -- the total number of arcs changed in th…
cs.DS2025
Simple Length-Constrained Expander Decompositions
Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz +1
Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an -length -expa…
cs.DS2021
Steiner Point Removal in Series-Parallel Graphs
D Ellis Hershkowitz, Jason Li
We study how to vertex-sparsify a graph while preserving both the graph's metric and structure. Specifically, we study the Steiner point removal (SPR) problem where we are given a…