Dani Dorfman

collaborators

3 papers

cs.DS2025

Expander Decomposition for Non-Uniform Vertex Measures

Daniel Agassy, Dani Dorfman, Haim Kaplan

A $(ϕ, ε)$ -expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_{1}, \dots, V_{k}$ with conductance $Φ (G [V_{i}]) \geq ϕ$ , such that…

cs.DS2025

Improved Tree Sparsifiers in Near-Linear Time

Daniel Agassy, Dani Dorfman, Haim Kaplan

A \emph{tree cut-sparsifier} $T$ of quality $α$ of a graph $G$ is a single tree that preserves the capacities of all cuts in the graph up to a factor of $α$ . A \emph{tree flow-spar…

cs.DS2025

Faster All-Pairs Optimal Electric Car Routing

Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2

We present a randomized $O ~ (n^{3.5})$ -time algorithm for computing \emph{optimal energetic paths} for an electric car between all pairs of vertices in an $n$ -vertex directed…