ﻻ يوجد ملخص باللغة العربية
Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantee for HHL algorithms have been left aside. In this paper we study HL and HHL from the complexity theory point of view. We prove that both HL and HHL are NP-hard, and present upper and lower bounds for the approximation ratios of greedy HHL algorithms used in practice. We also introduce a new variant of the greedy HHL algorithm and a proof that it produces small labels for graphs with small highway dimension.
Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a formulation of small size for the given problem. A useful approach for
In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An $s,t$ query computes the corresponding distance from the labels of $s$ and $t$ only, without looking at the input graph. Hub labels is a class of
In this note we investigate the complexity of the Minimum Label Alignment problem and we show that such a problem is APX-hard.
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,...,m} so that the order of labels (strictly) respec
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $textit{coordinator}$ model, where we have $k$ players