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 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.

A New Linear-Time Algorithm for Centroid Decomposition / Della Giustina, D.; Prezza, Nicola; Venturini, R.. - String Processing and Information Retrieval: 26th International Symposium, SPIRE 2019, Proceedings, (2019), pp. 274-282. (26th International Symposium on String Processing and Information Retrieval, SPIRE 2019, Segovia, Spain, October 7–9, 2019). [10.1007/978-3-030-32686-9_20].

### A New Linear-Time Algorithm for Centroid Decomposition

#### 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 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2019
978-3-030-32685-2
File in questo prodotto:
File
Centroid.pdf

Solo gestori archivio

Tipologia: Documento in Pre-print
Licenza: DRM (Digital rights management) non definiti
Dimensione 359.97 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11385/194103`