[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

General compact labeling schemes for dynamic trees

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

Let F be a function on pairs of vertices. An F-labeling scheme is composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute F(u, v) for any two vertices u and v directly from their labels. As applications for labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. This paper investigates labeling schemes for dynamic trees. We consider two dynamic tree models, namely, the leaf-dynamic tree model in which at each step a leaf can be added to or removed from the tree and the leaf-increasing tree model in which the only topological event that may occur is that a leaf joins the tree. A general method for constructing labeling schemes for dynamic trees (under the above mentioned dynamic tree models) was previously developed in Korman et al. (Theory Comput Syst 37:49–75, 2004). This method is based on extending an existing static tree labeling scheme to the dynamic setting. This approach fits many natural functions on trees, such as distance, separation level, ancestry relation, routing (in both the adversary and the designer port models), nearest common ancestor etc.. Their resulting dynamic schemes incur overheads (over the static scheme) on the label size and on the communication complexity. In particular, all their schemes yield a multiplicative overhead factor of Ω(log n) on the label sizes of the static schemes. Following (Korman et al., Theory Comput Syst 37:49–75, 2004), we develop a different general method for extending static labeling schemes to the dynamic tree settings. Our method fits the same class of tree functions. In contrast to the above paper, our trade-off is designed to minimize the label size, sometimes at the expense of communication. Informally, for any function k(n) and any static F-labeling scheme on trees, we present an F-labeling scheme on dynamic trees incurring multiplicative overhead factors (over the static scheme) of \(O(\log_{k(n)} n)\) on the label size and \(O(k(n)\log_{k(n)} n)\) on the amortized message complexity. In particular, by setting \(k(n) = n^{\epsilon}\) for any \(0 < \epsilon < 1\) , we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for the ancestry relation, the id-based and label-based nearest common ancestor relation and the routing function.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Afek Y., Awerbuch B., Plotkin S.A. and Saks M. (1996). Local management of a global resource in a communication. J. ACM 43: 1–19

    Article  MATH  MathSciNet  Google Scholar 

  2. Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: Proceedings of 14th ACM-SIAM Symposium on Discrete Algorithms (2003)

  3. Alstrup S., Gavoille C., Kaplan H. and Rauhe T. (2004). Nearest common ancestors: a survey and a new distributed algorithm. Theory Comput. Syst. 37: 441–456

    MATH  MathSciNet  Google Scholar 

  4. Alstrup, S., Holm, J., Thorup, M.: Maintaining center and median in dynamic trees. In: Proceedings of 7th Scandinavian Workshop on Algorithm Theory (2000)

  5. Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms (2001)

  6. Alstrup, S., Rauhe, T.: Improved labeling scheme for ancestor queries. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (2002)

  7. Breuer M.A. and Folkman J. (1967). An unexpected result on coding the vertices of a graph. J. Math. Anal. Appl. 20: 583–600

    Article  MATH  MathSciNet  Google Scholar 

  8. Breuer M.A. (1966). Coding the vertexes of a graph. IEEE Trans. Inf. Theory IT-12: 148–153

    Article  MathSciNet  Google Scholar 

  9. Cole, R., Hariharan, R.: Dynamic LCA Queries on Trees. In: Proceedings of 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 235–244 (1999)

  10. Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and Distance Queries via 2-hop Labels. In: Proceedings of 13th ACM-SIAM Symposium on Discrete Algorithms (2002)

  11. Cohen, E., Kaplan, H., Milo, T.: Labeling dynamic XML trees. In: Proceedings of 21st ACM Symposium on Principles of Database Systems (2002)

  12. Eppstein, D., Galil, Z., Italiano, G. F.: Dynamic Graph Algorithms. In: Atallah, M.J., (ed.) Algorithms and Theoretical Computing Handbook, Chap. 8. CRC Press, Boca Raton (1999)

    Google Scholar 

  13. Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proc. 28th Int. Colloq. on Automata, Languages and Prog. LNCS, vol. 2076, pp. 757–772 (2001)

  14. Fraigniaud, P., Gavoille, C.: A space lower bound for routing in trees. In: Proceedings of 19th Symposium on Theoretical Aspects of Computer Science (2002)

  15. Feigenbaum, J., Kannan, S.: Dynamic Graph Algorithms. In: Handbook of Discrete and Combinatorial Mathematics. CRC Press, Boca Raton (2000)

  16. Gavoille, C., Paul, C.: Split decomposition and distance labelling: an optimal scheme for distance hereditary graphs. In: Proceedings of European Conference on Combinatorics, Graph Theory and Applications (2001)

  17. Gavoille C. and Peleg D. (2003). Compact and localized distributed data structures. J. Distributed Comput. 16: 111–120

    Article  Google Scholar 

  18. Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate Distance Labeling Schemes. In: 9th European Symposium on Algorithms, August 2001, Aarhus, Denmark, pp. 476-488. SV-LNCS, vol. 2161 (2001)

  19. Gavoille C., Peleg D., Pérennes S. and Raz R. (2004). Distance labeling in graphs. J. Algorithms 53(1): 85–12

    Article  MATH  MathSciNet  Google Scholar 

  20. Holm J., Lichtenberg K. and Thorup M. (2001). Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4): 723–760

    Article  MathSciNet  Google Scholar 

  21. Kannan S., Naor M. and Rudich S. (1992). Implicit representation of graphs. SIAM J. Descrete Math. 5: 596–603

    Article  MATH  MathSciNet  Google Scholar 

  22. Kaplan, H., Milo, T.: Short and simple labels for small distances and other functions. In: Workshop on Algorithms and Data Structures (2001)

  23. Kaplan, H., Milo, T.: Parent and ancestor queries using a compact index. In: Proceedings of 20th ACM Symposium on Principles of Database Systems (2001)

  24. Kaplan, H., Milo, T., Shabo, R.: A Comparison of Labeling Schemes for Ancestor Queries. In: Proceeddings of 19th ACM-SIAM Symposium on Discrete Algorithms (2002)

  25. Katz M., Katz N.A., Korman A. and Peleg D. (2004). Labeling schemes for flow and connectivity. SIAM J. Comput. 34: 23–40

    Article  MATH  MathSciNet  Google Scholar 

  26. Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Proceedings of 17th Symposium on Theoretical Aspects of Computer Science, pp. 516–528 (2000)

  27. Korman, A.: General Compact Labeling Schemes for Dynamic Trees. ACM Comp. Research Repository. http://arxiv.org/abs/cs.DC/0605141

  28. Korman, A.: Labeling Schemes for Vertex Connectivity. In: Proc. 34th Int. Colloq. on Automata, Languages and Prog (2007)

  29. Korman, A., Kutten, S: Distributed verification of minimum spanning trees. In: Proceedings of 25th Annual Symposium on Principles of Distributed Computing (2006)

  30. Korman, A., Peleg, D.: Labeling Schemes for Weighted Dynamic Trees. In: Proc. 30th Int. Colloq. on Automata, Languages & Prog (2003)

  31. Korman A., Peleg D. and Rodeh Y. (2004). Labeling schemes for dynamic tree networks. Theory Comput. Syst. 37: 49–75

    Article  MATH  MathSciNet  Google Scholar 

  32. Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Proceedings of 25th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 30–41 (1999)

  33. Peleg, D.: Informative labeling schemes for graphs. In: Proceedings of 25th Symposium on Mathematical Foundations of Computer Science, pp. 579–588 (2000)

  34. Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)

  35. Sleator D.D. and Tarjan R. E. (1983). A data structure for dynamic trees. J. Comput. Syst. Sci. 26(1): 362–391

    Article  MATH  Google Scholar 

  36. Santoro N. and Khatib R. (1985). Labelling and implicit routing in networks. Comput. J. 28: 5–8

    Article  MATH  MathSciNet  Google Scholar 

  37. Thorup M. (2004). Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51: 993–1024

    Article  MathSciNet  Google Scholar 

  38. Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of 13th ACM Symposium on Parallel Algorithms and Architecture, pp. 1–10 (2001)

Download references

Author information

Authors and Affiliations

  1. Information Systems Group, Faculty of IE & M, The Technion, Haifa, 32000, Israel

    Amos Korman

Authors
  1. Amos Korman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amos Korman.

Additional information

Supported in part at the Technion by an Aly Kaufman fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Korman, A. General compact labeling schemes for dynamic trees. Distrib. Comput. 20, 179–193 (2007). https://doi.org/10.1007/s00446-007-0035-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-007-0035-z

Keywords

Search

Navigation