✦ LIBER ✦

On Reconstructing Rooted Trees

✍ Scribed by T. Andreae

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 667 KB
Volume: 62
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1063

No coin nor oath required. For personal study only.

✦ Synopsis

A probably very difficult question of Nash-Williams asks whether any two hypomorphic trees are isomorphic. In the present paper, we consider rooted trees rather than trees and give an affirmative answer to the corresponding version of Nash-Williams' question, i.e., we show that any two hypomorphic rooted trees are isomorphic. Further related results are given, together with applications to the reconstruction of unrooted trees. (\mathbb{C} 1994) Academic Press, Inc.

📜 SIMILAR VOLUMES

On path entropy functions for rooted tre

On path entropy functions for rooted trees

✍ A. Meir; J.W. Moon 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Ifu is a terminal node of a rooted tree T. with n terminal nodes, let h(u) = ~f (d(v)) where the sum is over all interior nodes v in the path from the root of T. to u, d(v) is the out-degree of v, and 1" is a non-negative cost function. The path entropy function h(T.) = ~h(u), where the sum is over

Parallel Shortcutting of Rooted Trees

✍ Mikkel Thorup 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 305 KB

First it is shown that for any rooted tree T with n vertices, and parameter m G n, there is a ''shortcutting'' set S of at most m arcs from the transitive closure Ž . T\* of T such for any ¨, w g T \*, there is a dipath in T j S from ¨to w of length Ž Ž .. Ž O ␣ m, n . An equivalent result has been

Reconstructing trees from two cards

✍ Manuel Welhan 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

## Abstract Let 𝒯 be the class of unlabeled trees. An unlabeled vertex‐deleted subgraph of a tree __T__ is called a card. A collection of cards is called a deck. We say that the tree __T__ has a deck __D__ if each card in __D__ can be obtained by deleting distinct vertices of __T__. If __T__ is the

On the Total Heights of Random Rooted Bi

On the Total Heights of Random Rooted Binary Trees

✍ L. Takacs 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

Optimal Labellings of Rooted Directed Tr

Optimal Labellings of Rooted Directed Trees

✍ Jia-yu Shao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 200 KB

We consider an optimal labelling problem for a rooted directed tree abbreviated . as ''RDT'' which is motivated by certain scheduling problem. We obtain several necessary and sufficient conditions for the optimal labellings of a RDT and give a polynomially bounded algorithm for constructing the opti

Twelve Countings with Rooted Plane Trees

✍ Martin Klazar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 357 KB