| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428434 | Information Processing Letters | 2007 | 5 Pages |
Abstract
The problem of on-line labelling is one of assigning integer labels in the range 1 to N to an input stream of at most N distinct items, drawn from a linearly ordered set, so that at each step the labels respect the ordering on the items. To maintain this constraint, items may have to be relabelled to accommodate new ones. With T(M,N) denoting the total number of relabellings that have to be performed for the first M inputs, it is known that for any given constant c in the range 0
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
