Reconstruction of rooted directed trees

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

Előnézet

Cikk, tanulmány, mű cybernetica_024_numb_002_249-262.pdf Letöltés (430kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	2019
Kötet:	24
Szám:	2
ISSN:	0324-721X
Oldalak:	pp. 249-262
Nyelv:	angol
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/64923/
DOI:	10.14232/actacyb.24.2.2019.5
Kulcsszavak:	Algoritmus
Megjegyzések:	Bibliogr.: p. 261-262. ; összefoglalás angol nyelven
Szakterület:	01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma:	2020. már. 17. 11:01
Utolsó módosítás:	2022. jún. 21. 08:49
URI:	http://acta.bibl.u-szeged.hu/id/eprint/64711

Bővebben:

Tétel nézet