Reconstruction of rooted directed trees

Bartha Dénes: Reconstruction of rooted directed trees. In: Acta cybernetica, (24) 2. pp. 249-262. (2019)

[thumbnail of cybernetica_024_numb_002_249-262.pdf]
Preview
Cikk, tanulmány, mű
cybernetica_024_numb_002_249-262.pdf

Download (430kB) | Preview

Abstract

Let T be a rooted directed tree on n vertices, rooted at v. The rooted subtree frequency vector (RSTF-vector ) of T with root v, denoted by rstf(T, v) is a vector of length n whose entry at position k is the number of subtrees of T that contain v and have exactly k vertices. In this paper we present an algorithm for reconstructing rooted directed trees from their rooted subtree frequencies (up to isomorphism). We show that there are examples of nonisomorphic pairs of rooted directed trees that are RSTF-equivalent, that is they share the same rooted subtree frequency vectors. We have found all such pairs (groups) for small sizes by using exhaustive computer search. We show that infinitely many nonisomorphic RSTF-equivalent pairs of trees exist by constructing infinite families of examples.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2019
Volume: 24
Number: 2
ISSN: 0324-721X
Page Range: pp. 249-262
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/64923/
DOI: 10.14232/actacyb.24.2.2019.5
Uncontrolled Keywords: Algoritmus
Additional Information: Bibliogr.: p. 261-262. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2020. Mar. 17. 11:01
Last Modified: 2022. Jun. 21. 08:49
URI: http://acta.bibl.u-szeged.hu/id/eprint/64711

Actions (login required)

View Item View Item