TY - GEN

T1 - Distance labeling in graphs

AU - Gavoille, Cyril

AU - Peleg, David

AU - Pérennes, Stéphane

AU - Raz, Ran

PY - 2001

Y1 - 2001

N2 - We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional information). Our main interest is in the minimal length of labels needed in different cases. We obtain upper bounds and (most importantly) lower bounds for several interesting families of graphs. In particular, our main results are the following: For general graphs, the length needed is &THgr;(n). For trees, the length needed is &THgr;(log 2 n). For planar graphs, we show an upper bound of &Ogr;(√n log n) and a lower bound of &OHgr; (n1/3). For bounded degree graphs, we show a lower bound of &OHgr;(√n). The upper bounds for planar graphs and for trees follow by a more general upper bound for graphs with a r(n)- separator. The two lower bounds, however, are obtained by two different arguments that may be interesting in their own right. We also show some lower bounds on the length of the labels, even if it is only required that distances be approximated to a multiplicative factor s. For example, we show that for general graphs the required length is &OHgr;(n). We also consider the problem of the time complexity of the distance function once the labels are computed. We show that there are graphs with optimal labels of length 3 log n, such that if we use any labels with fewer than n bits per label, computing the distance function requires exponential time. A similar result is obtained for planar and bounded degree graphs.

AB - We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional information). Our main interest is in the minimal length of labels needed in different cases. We obtain upper bounds and (most importantly) lower bounds for several interesting families of graphs. In particular, our main results are the following: For general graphs, the length needed is &THgr;(n). For trees, the length needed is &THgr;(log 2 n). For planar graphs, we show an upper bound of &Ogr;(√n log n) and a lower bound of &OHgr; (n1/3). For bounded degree graphs, we show a lower bound of &OHgr;(√n). The upper bounds for planar graphs and for trees follow by a more general upper bound for graphs with a r(n)- separator. The two lower bounds, however, are obtained by two different arguments that may be interesting in their own right. We also show some lower bounds on the length of the labels, even if it is only required that distances be approximated to a multiplicative factor s. For example, we show that for general graphs the required length is &OHgr;(n). We also consider the problem of the time complexity of the distance function once the labels are computed. We show that there are graphs with optimal labels of length 3 log n, such that if we use any labels with fewer than n bits per label, computing the distance function requires exponential time. A similar result is obtained for planar and bounded degree graphs.

KW - Algorithms

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=57749210158&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57749210158&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:57749210158

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 210

EP - 219

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -