3 papers
cs.DS2026
Dynamic Edge Coloring of Forests
Haim Kaplan, David Naori, Yaniv Sadeh
In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree with at most colors, under edge updates. A prominent objective is to minimize…
cs.DS2026
Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
Yaniv Sadeh, Haim Kaplan
We study the maintenance of a -edge-coloring () in a fully dynamic graph with maximum degree . We focus on minimizing \emph{recourse} which equals the numbe…
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…