Abstract
The centroid of a tree is a node that, when removed, breaks the tree in connected components of size at most half of that of the original tree. By recursing this procedure on the components, one obtains the centroid decomposition of the tree, also known as centroid tree. The centroid tree has logarithmic height and its construction is a powerful pre-processing step in several tree-processing algorithms. The folklore recursive algorithm for computing the centroid tree runs in \(O(n\log n)\) time. To the best of our knowledge, the only result claiming O(n) time is unpublished and relies on (dynamic) heavy path decomposition of the original tree. In this short paper, we describe a new simple and practical linear-time algorithm for the problem based on the idea of applying the folklore algorithm to a suitable decomposition of the original tree.
Partially supported by the project MIUR-SIR CMACBioSeq (“Combinatorial methods for analysis and compression of biological sequences”) grant n. RBSI146R5L and by the project MIUR-PRIN 2017 “Algorithms, Data Structures and Combinatorics for Machine Learning”.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
Note that the centroid decomposition does not depend on how the tree is rooted.
References
Aronov, B., et al.: Data structures for halfplane proximity queries and incremental voronoi diagrams. In: Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN), pp. 80–92 (2006). https://doi.org/10.1007/11682462_12
Bender, M.A., Farach-Colton, M., Kuszmaul, B.C.: Cache-oblivious string b-trees. In: Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 233–242 (2006). https://doi.org/10.1145/1142351.1142385
Brodal, G.S., Fagerberg, R., Pedersen, C.N.S., Östlin, A.: The complexity of constructing evolutionary trees using experiments. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), pp. 140–151 (2001). https://doi.org/10.1007/3-540-48224-5_12
Brodal, G.S., Fagerberg, R., Pedersen, C.N.S., Östlin, A.: The complexity of constructing evolutionary trees using experiments. Technical Report BRICS-RS-01-1, BRICS, Department of Computer Science, University of Aarhus (2001). https://www.brics.dk/RS/01/1/BRICS-RS-01-1.pdf
Ferragina, P.: On the weak prefix-search problem. Theoret. Comput. Sci. 483, 75–84 (2013). https://doi.org/10.1016/j.tcs.2012.06.011
Ferragina, P., Venturini, R.: Compressed cache-oblivious string b-tree. ACM Trans. Algorithms (TALG) 12(4), 52:1–52:17 (2016). https://doi.org/10.1145/2903141
Gagie, T., Hermelin, D., Landau, G.M., Weimann, O.: Binary jumbled pattern matching on trees and tree-like structures. Algorithmica 73(3), 571–588 (2015). https://doi.org/10.1007/s00453-014-9957-6
Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Trans. Algorithms (TALG) 2(4), 510–534 (2006)
Guibas, L.J., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problemsinside triangulated simple polygons. Algorithmica 2, 209–233 (1987). https://doi.org/10.1007/BF01840360
Jordan, C.: Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik 70, 185–190 (1869)
Kociumaka, T., Pachocki, J., Radoszewski, J., Rytter, W., Walen, T.: Efficient counting of square substrings in a tree. Theoret. Comput. Sci. 544, 60–73 (2014). https://doi.org/10.1016/j.tcs.2014.04.015
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362–391 (1983). https://doi.org/10.1016/0022-0000(83)90006-5
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Della Giustina, D., Prezza, N., Venturini, R. (2019). A New Linear-Time Algorithm for Centroid Decomposition. In: Brisaboa, N., Puglisi, S. (eds) String Processing and Information Retrieval. SPIRE 2019. Lecture Notes in Computer Science(), vol 11811. Springer, Cham. https://doi.org/10.1007/978-3-030-32686-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-32686-9_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32685-2
Online ISBN: 978-3-030-32686-9
eBook Packages: Computer ScienceComputer Science (R0)