We present a near linear time algorithm for constructing hierarchical nets in finite metric
spaces with constant doubling dimension. This data-structure is then applied to obtain …

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be
covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a …

This paper studies labeling schemes for flow and connectivity functions. A flow labeling
scheme using O(\logn⋅̂ω+\log^2n)-bit labels is presented for general n-vertex graphs with …

This survey concerns the role of data structures for compactly storing and representing
various types of information in a localized and distributed fashion. Traditional approaches to …

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a
sequential setting. Given a graph and a tree that spans it, the algorithm is required to check …

This paper deals with the length of a Robertson–Seymour's tree-decomposition. The tree-
length of a graph is the largest distance between two vertices of a bag of a tree …

We consider four problems on distance estimation and object location: low-stretch routing
schemes [37], distance labeling [14], searchable small worlds [22], and triangulation-based …

We consider labeling schemes for trees, supporting various relationships between nodes at
small distance. For instance, we show that given a tree T and an integer k we can assign …

Proof-labeling schemes, introduced by Korman et al.(Distrib Comput 22 (4): 215–233, 2010.
https://doi. org/10.1007/s00446-010-0095-3), are a mechanism to certify that a network …

Abstract δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-
point condition: for any four points u, v, w, x, the two larger of the distance sums d (u, v)+ d …