9 citations · 9 across the 7 of their papers we have counts for
5 papers · 1 filter
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 t…
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 number…
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…
Caching Connections in Matchings
Yaniv Sadeh, Haim Kaplan
Motivated by the desire to utilize a limited number of configurable optical switches by recent advances in Software Defined Networks (SDNs), we define an online problem which we ca…
Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
Yaniv Sadeh, Haim Kaplan
Binary search trees (BSTs) are one of the most basic and widely used data structures. The best static tree for serving a sequence of queries (searches) can be computed by dynamic p…