3 papers
cs.DS2026
Planar Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz, Richard Z Huang
In length-constrained minimum spanning tree (MST) we are given an -node graph with edge weights and edge lengths $l: E \to \mathbb{Z}…
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 -exp…