arXiv preprint ·
A Tight Second-Order Lower Bound for Routing Labels in Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $\log_2 n+O((\log_2\log_2 n)^2)$, whereas the previous lower bound was $\log_2 n+Ω(\log_2\log_2 n)$. We prove that every scheme for all $n$-vertex trees needs a label of length $\log_2 n+Ω((\log_2\log_2 n)^2)$ for every sufficiently large $n$. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Online Stochastic Allocation with Increasing Returns
On Extensions of the Unanimous Vote Problem
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.