pipette
ENEnglish

A Tight Second-Order Lower Bound for Routing Labels in Trees

Hanqing Li

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 6 pages, no figures