pipette
ESEspañol

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

Hanqing Li

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 6 pages, no figures