110 citations · 483 across the 37 of their papers we have counts for
4 papers · 2 filters
An Optimal Labeling Scheme for Ancestry Queries
Pierre Fraigniaud, Amos Korman
An ancestry labeling scheme assigns labels (bit strings) to the nodes of rooted trees such that ancestry queries between any two nodes in a tree can be answered merely by looking a…
Approximating the Statistics of various Properties in Randomly Weighted Graphs
Yuval Emek, Amos Korman, Yuval Shavitt
Consider the setting of \emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over…
Compact Ancestry Labeling Schemes for Trees of Small Depth
Pierre Fraigniaud, Amos Korman
An {\em ancestry labeling scheme} labels the nodes of any tree in such a way that ancestry queries between any two nodes in a tree can be answered just by looking at their correspo…
On the Additive Constant of the k-server Work Function Algorithm
Yuval Emek, Pierre Fraigniaud, Amos Korman +1
We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a cons…