Back to Search
Start Over
Proximity-preserving labeling schemes
- Source :
- Journal of Graph Theory; March 2000, Vol. 33 Issue: 3 p167-176, 10p
- Publication Year :
- 2000
-
Abstract
- This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity-preserving labeling scheme. It is shown that, for the class of n-vertex weighted trees with M-bit edge weights, there exists such a proximity-preserving labeling scheme using O(M log n + log<SUP>2</SUP>n) bit labels. For the family of all n-vertex unweighted graphs, a labeling scheme is proposed that using O(log<SUP>2</SUP> n · κ · n<SUP>1/κ</SUP>) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of <UEQN NOTAT="TEX" LOC="INLINE"> $\sqrt{8\kappa }.$</UEQN> In particular, using O(log<SUP>3</SUP>n) bit labels, the scheme can provide estimates accurate up to a factor of <UEQN NOTAT="TEX" LOC="INLINE">$\sqrt{2 \log n}$.</UEQN> (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167176, 2000
Details
- Language :
- English
- ISSN :
- 03649024 and 10970118
- Volume :
- 33
- Issue :
- 3
- Database :
- Supplemental Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Periodical
- Accession number :
- ejs2069211
- Full Text :
- https://doi.org/10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5