The Value of Steiner Hubs in Two-Hop Distance Labeling
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying arbitrary real values. On no family is the value of that freedom known. We determine it on $\ell_1$ products of betweenness-free metrics, those with no point between two others, a class containing every Hamming graph. The freedom is worth nothing when the factors have at most three letters, while from four letters on the largest saving is polynomial in the size of the product, attained on products of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01106
curl -X POST /api/v1/records/arxiv/2611.01106/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01106/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'