110 citations · 483 across the 37 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016★ 5 cited
An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
Pierre Fraigniaud, Amos Korman
In this paper we solve the ancestry-labeling scheme problem which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so that ancestry queries be…
cs.DS2016★ 2 cited
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
Lucas Boczkowski, Uriel Feige, Amos Korman +1
We consider a search problem on trees in which the goal is to find an adversarially placed treasure, while relying on local, partial information. Specifically, each node in the tre…