Document Open Access Logo

Sublinear Distance Labeling

Authors Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Ely Porat

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.5.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Stephen Alstrup
Søren Dahlgaard
Mathias Bæk Tejs Knudsen
Ely Porat

Cite As Get BibTex

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear Distance Labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.5

Abstract

A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs.

We present a O(n/D * log^2(D)) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Omega(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results:

1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et. al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Omega(n) bits, Moon [Proc. of Glasgow Math. Association 1965].

2. For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size
O(n/r * polylog(r*log(n))/log(n)) for r >= 2. This improves on the current best bound of O(n/r) by Alstrup et al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r=2.

Subject Classification

Keywords
  • Graph labeling schemes
  • Distance labeling
  • Graph theory
  • Sparse graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Abiteboul, H. Kaplan, and T. Milo. Compact labeling schemes for ancestor queries. In Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 547-556, 2001. Google Scholar
  2. I. Abraham, S. Chechik, and C. Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proc. 44th Annual ACM Symp. on Theory of Computing (STOC), pages 1199-1218, 2012. Google Scholar
  3. R. Agarwal, P. B. Godfrey, and S. Har-Peled. Approximate distance queries and compact routing in sparse graphs. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications, pages 1754-1762, 2011. Google Scholar
  4. T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM International Conference on Management of Data (SIGMOD), pages 349-360, 2013. URL: http://dx.doi.org/10.1145/2463676.2465315.
  5. S. Alstrup, S. Dahlgaard, and M. B. T. Knudsen. Optimal induced universal graphs and labeling schemes for trees. In Proc. 56th Annual Symp. on Foundations of Computer Science (FOCS), 2015. Google Scholar
  6. S. Alstrup, S. Dahlgaard, M. B. T. Knudsen, and E. Porat. Sublinear distance labeling for sparse graphs. CoRR, abs/1507.02618, 2015. URL: http://arxiv.org/abs/1507.02618.
  7. S. Alstrup, C. Gavoille, E. B. Halvorsen, and H. Petersen. Simpler, faster and shorter labels for distances in graphs. In Proc. 27th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 338-350, 2016. Google Scholar
  8. S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick. Adjacency labeling schemes and induced-universal graphs. In Proc. of the 47th Annual ACM Symp. on Theory of Computing (STOC), 2015. Google Scholar
  9. S. Alstrup and T. Rauhe. Small induced-universal graphs and compact implicit graph representations. In Proc. 43rd Annual Symp. on Foundations of Computer Science (FOCS), pages 53-62, 2002. Google Scholar
  10. F. Bazzaro and C. Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 309(11):3465-3484, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.12.091.
  11. B. Bollobás, D. Coppersmith, and M. Elkin. Sparse distance preservers and additive spanners. SIAM J. Discrete Math., 19(4):1029-1055, 2005. See also SODA'03. URL: http://dx.doi.org/10.1137/S0895480103431046.
  12. M. A. Breuer. Coding the vertexes of a graph. IEEE Trans. on Information Theory, IT-12:148-153, 1966. Google Scholar
  13. M. A. Breuer and J. Folkman. An unexpected result on coding vertices of a graph. J. of Mathemathical analysis and applications, 20:583-600, 1967. Google Scholar
  14. V. D. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. In 24^th Annual ACM Symp. on Computational Geometry (SoCG), pages 59-68, 2008. URL: http://dx.doi.org/10.1145/1377676.1377687.
  15. V. D. Chepoi, F. F. Dragan, and Y. Vaxès. Distance and routing labeling schemes for non-positively curved plane graphs. J. of Algorithms, 61(2):60-88, 2006. URL: http://dx.doi.org/10.1016/j.jalgor.2004.07.011.
  16. B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics, 131:129-150, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(02)00421-3.
  17. D. Delling, A. V. Goldberg, R. Savchenko, and R. F. Werneck. Hub labels: Theory and practice. In 13^th International Symp. on Experimental Algorithms (SEA), pages 259-270, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07959-2_22.
  18. P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194-203, 1975. Google Scholar
  19. M. Elkin, A. Filtser, and O. Neiman. Prioritized metric structures and embedding. In Proc. of the 47th Annual ACM Symp. on Theory of Computing (STOC), pages 489-498, 2015. Google Scholar
  20. M. Elkin and S. Pettie. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. In Proc. of the 26th Annual Symp. on Discrete Algorithms (SODA), pages 805-821, 2015. Google Scholar
  21. C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. In Proc. of the 9th annual European Symp. on Algorithms (ESA), pages 476-488, 2001. Google Scholar
  22. C. Gavoille and C. Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. Google Scholar
  23. C. Gavoille and C. Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM J. Discrete Math., 22(3):1239-1258, 2008. URL: http://dx.doi.org/10.1137/050635006.
  24. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. J. of Algorithms, 53(1):85-112, 2004. See also SODA'01. URL: http://dx.doi.org/10.1016/j.jalgor.2004.05.002.
  25. P. Gawrychowski, A. Kosowski, and P. Uznanski. Even simpler distance labeling for (sparse) graphs. CoRR, abs/1507.06240, 2015. URL: http://arxiv.org/abs/1507.06240.
  26. R. L. Graham and H. O. Pollak. On embedding graphs in squashed cubes. In Lecture Notes in Mathematics, volume 303. Springer-Verlag, 1972. Google Scholar
  27. A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual Symp. on Foundations of Computer Science (FOCS), pages 534-543, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238226.
  28. A. Gupta, A. Kumar, and R. Rastogi. Traveling with a pez dispenser (or, routing issues in mpls). SIAM J. on Computing, 34(2):453-474, 2005. See also FOCS'01. Google Scholar
  29. R. Jin, N. Ruan, Y. Xiang, and V. Lee. A highway-centric labeling approach for answering distance queries on large sparse graphs. In ACM International Conference on Management of Data (SIGMOD), pages 445-456, May 2012. URL: http://dx.doi.org/10.1145/2213836.2213887.
  30. S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. SIAM J. Disc. Math., pages 596-603, 1992. See also STOC'88. Google Scholar
  31. M. Katz, N. A. Katz, A. Korman, and D. Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23-40, 2004. See also SODA'02. URL: http://dx.doi.org/10.1137/S0097539703433912.
  32. R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In 47th Annual Symp. on Foundations of Computer Science (FOCS), pages 119-132, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.9.
  33. J. W. Moon. On minimal n-universal graphs. Proc. of the Glasgow Mathematical Association, 7(1):32-33, 1965. Google Scholar
  34. J. H. Müller. Local structure in graph classes. PhD thesis, Georgia Institute of Technology, 1988. Google Scholar
  35. D. Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167-176, 2000. Google Scholar
  36. K. Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proc. of the 36th Annual ACM Symp. on Theory of Computing (STOC), pages 281-290, 2004. URL: http://dx.doi.org/10.1145/1007352.1007399.
  37. M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. See also FOCS'01. URL: http://dx.doi.org/10.1145/1039488.1039493.
  38. M. Thorup and U. Zwick. Approximate distance oracles. J. of the ACM, 52(1):1-24, 2005. See also STOC'01. Google Scholar
  39. P. M. Winkler. Proof of the squashed cube conjecture. Combinatorica, 3(1):135-139, 1983. URL: http://dx.doi.org/10.1007/BF02579350.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact