Distance and Routing Labeling Schemes for Cube-Free Median Graphs
- PDF / 899,958 Bytes
- 45 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 231 Views
Distance and Routing Labeling Schemes for Cube-Free Median Graphs Victor Chepoi1 · Arnaud Labourel1
· Sébastien Ratel1
Received: 26 July 2019 / Accepted: 28 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes label the vertices of a graph in a such a way that given the labels of a source node and a destination node, it is possible to compute efficiently the port number of the edge from the source that heads in the direction of the destination. One of important problems is finding natural classes of graphs admitting distance and/or routing labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance and routing labeling schemes with labels of O(log3 n) bits. Keywords Median graphs · Labeling schemes · Distributed distance computation
1 Introduction Classical network representations are usually global in nature. In order to derive a useful piece of information, one must access to a global data structure representing the entire network even if the needed information only concerns few nodes. Nowadays, with networks getting bigger and bigger, the need for locality is more important than ever. Indeed, in several cases, global representations are impractical and network rep-
The short version of this paper appeared at MFCS 2019.
B
Arnaud Labourel [email protected] Victor Chepoi [email protected] Sébastien Ratel [email protected]
1
LIS, Aix Marseille Université, CNRS, Université de Toulon, Marseille, France
123
Algorithmica
resentation must be distributed. The notion of (distributed) labeling scheme has been introduced [15,36,42,50,51] in order to meet this need. A (distributed) labeling scheme is a scheme maintaining global information on a network using local data structures (or labels) assigned to nodes of the network. Their goal is to locally store some useful information about the network in order to answer a specific query concerning a pair of nodes by only inspecting the labels of the two nodes. Motivation for such localized data structure in distributed computing is surveyed and widely discussed in [50]. The predefined queries can be of various types such as distance, adjacency, or routing. The quality of a labeling scheme is measured by the size of the labels of nodes and the time required to answer queries. Trees with n vertices admit adjacency and routing labeling schemes with size of labels and query time O(log n) and distance labeling schemes with size of labels and query time O(log2 n), and this is asymptotically optimal. Finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size is an important and challengin
Data Loading...
