Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes (such as distance or adjacency) can be computed by examining their labels alone. For the particular case of trees, following a long line of research, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS '15], nearest common ancestor labeling [SODA '14], and ancestry labeling [SICOMP '06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size 1/4\log^2n+o(\log^2n), matching (up to low order terms) the recent 1/4\log^2n-\Oh(\log n) lower bound [ICALP '16]. Prior to our work, all distance labeling schemes for trees could be reinterpreted as universal trees. A tree T is said to be universal if any tree on $n$ nodes can be found as a subtree of T. A universal tree with |T| nodes implies a distance labeling scheme with label size \log |T|. In 1981, Chung et al. proved that any distance labeling scheme based on universal trees requires labels of size 1/2\log^2 n -\log n \cdot \log\log n+\Oh(\log n). Our scheme is the first to break this lower bound, showing a separation between distance labeling and universal trees. The θ (log^{2 n}) barrier for distance labeling in trees has led researchers to consider distances bounded by k. The size of such labels was shown to be \log n+\Oh(k\sqrt{\log n}) in [WADS '01], and then improved to \log n+\Oh(k^2(\log(k\log n)) in [SODA '03] and finally to \log n+\Oh(k\log(k\log(n/k))) in [PODC '07]. We show how to construct labels whose size is the minimum between \log n+\Oh(k\log((\log n)/k)) and \Oh(\log n \cdot \log(k/\log n)). We complement this with almost tight lower bounds of \log n+\Omega(k\log(\log n / (k\log k))) and \Omega(\log n \cdot \log(k/\log n)). Finally, we consider (1+\eps)-approximate distances. We show that the recent labeling scheme of [ICALP '16] can be easily modified to obtain an \Oh(\log(1/\eps)\cdot \log n) upper bound and we prove a matching \Omega(\log(1/\eps)\cdot \log n) lower bound.

The virtual resources of 5G networks are expected to scale and support migration to other locations within the substrate. In this context, a configuration for 5G network slices details the instantaneous mapping of the virtual resources across all slices on the substrate, and a feasible configuration satisfies the Service-Level Objectives (SLOs) without overloading the substrate. Reconfiguring a network from a given source configuration to the desired target configuration involves identifying an ordered sequence of feasible configurations from the source to the target. The proposed solutions for finding such a sequence are optimized for data centers and cannot be used as-is for reconfiguring 5G network slices. We present Matryoshka, our divide-and-conquer approach for finding a sequence of feasible configurations that can be used to reconfigure 5G network slices. Unlike previous approaches, Matryoshka also considers the bandwidth and latency constraints between the network functions of network slices. Evaluating Matryoshka required a dataset of pairs of source and target configurations. Because such a dataset is currently unavailable, we analyze proof of concept roll-outs, trends in standardization bodies, and research sources to compile an input dataset. On using Matryoshka on our dataset, we observe that it yields close-to-optimal reconfiguration sequences 10X faster than existing approaches.

Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. However, in practice, they may have thousands of cycles, as they are often created in a crowd-sourced way. Since these cycles represent logical fallacies, they need to be removed for many web applications. In this paper, we address the problem of breaking cycles while preserving the logical structure (hierarchy) of a directed graph as much as possible. Existing approaches for this problem either need manual intervention or use heuristics that can critically alter the taxonomy structure. In contrast, our approach infers graph hierarchy using a range of features, including a Bayesian skill rating system and a social agony metric. We also devise several strategies to leverage the inferred hierarchy for removing a small subset of edges to make the graph acyclic. Extensive experiments demonstrate the effectiveness of our approach.