A Tight Second-Order Lower Bound for Routing Labels in Trees
En palabras de los autores
In the designer-port routing-labeling problem, every vertex of a rooted tree receives a binary label and the child edges receive distinct port numbers. Given only the labels of a source and a destination, a decoder must return the first port on their path. Gawrychowski, Janczewski, and Lopuszanski gave labels of length , whereas the previous lower bound was . We prove that every scheme for all -vertex trees needs a label of length for every sufficiently large . The result allows arbitrary port assignments and imposes no computational restriction on either the encoder or the decoder. Thus the second-order term in the optimal worst-case label length is determined up to constant factors.
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 6 pages, no figures