𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithmic Aspects of Tree Amalgamation

✍ Scribed by Sebastian Böcker; David Bryant; Andreas W.M. Dress; Mike A. Steel

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
129 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

The amalgamation of leaf-labeled trees into a single (super)tree that "displays" each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomialtime algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.

📜 SIMILAR VOLUMES

Conference on algorithmic aspects of com
Conference on algorithmic aspects of combinatorics
📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 80 KB

ects of Combinatorics ects of Combinatorics wi!J be bia, Canada, ay 1'7-21, 'hW6. y the Simon Fraser ersity of Victoria and the University of stish Columbia. speakers are tentatively schedul ster sessions will be arrar-bed.

ALGORITHMIC ASPECTS OF ADAPTIVE MULTIGRI
ALGORITHMIC ASPECTS OF ADAPTIVE MULTIGRID FINITE ELEMENT ANALYSIS
✍ S. LOPEZ; R. CASCIARO 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB 👁 2 views

This paper describes the algorithmic aspects of a multigrid solver based on the adaptive generation of a sequence of discretizing meshes. Non-uniform discretization is obtained by conÿning ÿner meshes to progressively smaller subdomains. New meshes are generated through bisection reÿnement according

Algorithmic Problems for Amalgams of Fin
Algorithmic Problems for Amalgams of Finite Semigroups
✍ Mark V. Sapir 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 118 KB

We prove that there exists an amalgam of two finite 4-nilpotent semigroups such that the corresponding amalgamated product has an undecidable word problem. We also show that the problem of embeddability of finite semigroup amalgams in any semigroups and the problem of embeddability of finite semigro