Haim Kaplan

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

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…

cs.DS2025

Search Trees on Trees via LP

Yaniv Sadeh, Haim Kaplan, Uri Zwick

We consider the problem of computing optimal search trees on trees (STTs). STTs generalize binary search trees (BSTs) in which we search nodes in a path (linear order) to search tr…