Search: onr:"swepub:oai:DiVA.org:su-206196" >
Compatibility of pa...
Abstract
Subject headings
Close
- The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T∗ of T exists such that T∗ and P are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with P. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps.
Subject headings
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Keyword
- Hierarchy
- Split system
- Phylogenetic tree
- Partition
- Compatibility
- Recognition algorithm
- Fitch map
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database