𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reconstructing trees from two cards

✍ Scribed by Manuel Welhan

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
204 KB
Volume
63
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 only unlabeled tree that has the deck D, we say that T is 𝒯‐reconstructible from D. We want to know how large of a deck D is necessary for T to be 𝒯‐reconstructible. We define 𝒯rn(T) as the minimum number of cards in a deck D such that T is 𝒯‐reconstructible from D. It is known that
𝒯rn(T)≤3, but it is conjectured that 𝒯rn(T)≤2 for all trees T. We prove that the conjecture holds for all homeomorphically irreducible trees. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 243–257, 2010

📜 SIMILAR VOLUMES

Tree Reconstruction from Multi-State Cha
Tree Reconstruction from Multi-State Characters
✍ Charles Semple; Mike Steel 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 134 KB

In evolutionary biology, a character is a function χ from a set X of present-day species into a finite set of states. Suppose the species in X have evolved according to a bifurcating tree . Biologists would like to use characters to infer this tree. Assume that χ is the result of an evolutionary pro

Riverflow reconstruction from tree rings
Riverflow reconstruction from tree rings in southern Britain
✍ Jones, P. D. ;Briffa, K. R. ;Pilcher, J. R. 📂 Article 📅 1984 🏛 Wiley (John Wiley & Sons) ⚖ 906 KB

Ring widths of oak trees (Quercus petraea Liebl. and Quercus robur L.) from a network of seven sites in southern Britain and northern France are used to reconstruct riverflow for three river catchments in southern Britain. These dendrohydrological reconstructions, made using a principal components r

The reconstruction of a tree from its nu
The reconstruction of a tree from its number deck
✍ I Krasikov; J Schönheim 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 555 KB

Those trees are characterized which are reconstructible f~om the knowledge of the sizes of the connected components in each maximal subgraph. II est connu que la conjecture de Ulam est vraie pour les arbres. Dam un language d~ Harary ceci s'exprime de la fa~n suivante: Si les n for6ts, qu'on a obt

Image reconstructions from two orthogona
Image reconstructions from two orthogonal projections
✍ Yuanmei Wang; Pheng Ann Heng; Friedrich M. Wahl 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract A vector entropy optimization‐based neural network approach is presented to handle image reconstructions from two orthogonal projections. An accurate and parallel reconstruction is attained with this method allowing parallel implementation. This is an attempt to extract the image inform