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

Prezza N.;
2019

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.
2019
978-3-030-32685-2
File in questo prodotto:
File Dimensione Formato  
Centroid.pdf

Solo gestori archivio

Tipologia: Documento in Pre-print
Licenza: DRM (Digital rights management) non definiti
Dimensione 359.97 kB
Formato Adobe PDF
359.97 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/194103
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact