β Scribed by Chang-Chun Lu; Shi-Chun Tsai
No coin nor oath required. For personal study only.
A writer stores some data in memory accessible via address lines. If an adversary permutes the address lines after the writer leaves the message, then how can a reader find the permutation? This is the so-called unscrambling address lines problem of Broder et al. [SODA'99, 1999, pp. 870-871]. By a divide-and-conquer approach, we give a very simple algorithm to recover the permutation. Our method is much easier to understand than Broder et al.'s previous ad hoc solution.
π SIMILAR VOLUMES
## Abstract Whitney's theorem on line graphs is extended to the class of generalized line graphs defined by Hoffman.
we consider a variant of on-line scheduling, where partial information on future jobs is known beforehand. Assume that the last job will be the longest (with the longest execution time). We provide the beat possible on-line algorithms with competitive ratios \/z and 3/2, respectively, for m = 2 and