Abstract
Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits.
The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumerate argument, which is of independent interest, we show the space requirement of the oracle is optimal to within lower order terms for all treewidths. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pair shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O(k 2log3 k) time. Particularly, for the class of graphs of our interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barbay, J., Aleardi, L.C., He, M., Ian Munro, J.: Succinct representation of labeled graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 316–328. Springer, Heidelberg (2007)
Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: Proceedings of 14th ACM-SIAM Symposium on Discrete Algorithms, SODA 2003, pp. 679–688 (2003)
Blelloch, G.E., Farzan, A.: Succinct representations of separable graphs. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 138–150. Springer, Heidelberg (2010)
Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: van Leeuwen, J. (ed.) WG 1988. LNCS, vol. 344, pp. 1–10. Springer, Heidelberg (1989)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1–23 (1993)
Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 1–14. Springer, Heidelberg (2006)
Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 514–523 (2006)
Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37, 641–670 (2007)
Farzan, A.: Succinct Representation of Trees and Graphs. PhD thesis, School of Computer Science, University of Waterloo (2009)
Farzan, A., Ian Munro, J.: Succinct representations of arbitrary graphs. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol. 5193, pp. 393–404. Springer, Heidelberg (2008)
Gavoille, C., Hanusse, N.: On Compact Encoding of Pagenumber k Graphs. Discrete Mathematics & Theoretical Computer Science 10(3), 23–34 (2008)
Gavoille, C., Labourel, A.: Shorter implicit representation for planar graphs and bounded treewidth graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 582–593. Springer, Heidelberg (2007)
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, SODA 2003, pp. 841–850 (2003)
Harary, F., Robinson, R.W., Schwenk, A.J.: Twenty-step algorithm for determining the asymptotic number of trees of various species: Corrigenda. Journal of the Australian Mathematical Society 41(A), 325 (1986)
He, M., Ian Munro, J., Srinivasa Rao, S.: Succinct Ordinal Trees Based on Tree Covering. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 509–520. Springer, Heidelberg (2007)
Nitto, I., Venturini, R.: On compact representations of all-pairs-shortest-path-distance matrices. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 166–177. Springer, Heidelberg (2008)
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farzan, A., Kamali, S. (2011). Compact Navigation and Distance Oracles for Graphs with Small Treewidth. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-22006-7_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22005-0
Online ISBN: 978-3-642-22006-7
eBook Packages: Computer ScienceComputer Science (R0)