Counting cherry reduction sequences is counting linear extensions (in phylogenetic tree-child networks)
Orchard and tree-child networks share an important property with phylogenetic trees: they can be completely reduced to a single node by iteratively deleting cherries and reticulated cherries. As it is the case with phylogenetic trees, the number of ways in which this can be done gives information about the topology of the network. Here, we show that the problem of computing this number in tree-child networks is akin to that of finding the number of linear extensions of the poset induced by each network, and give an algorithm based on this reduction whose complexity is bounded in terms of the level of the network.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Cherry Yield Forecast: Harvest Prediction for Individual Sweet Cherry Trees
This paper is part of a publication series from the For5G project that has the goal of creating digital twins of sweet cherry trees. At the beginning a brief overview of the revious work in this project is provided. Afte…
An Application of Deep Learning for Sweet Cherry Phenotyping using YOLO Object Detection
Tree fruit breeding is a long-term activity involving repeated measurements of various fruit quality traits on a large number of samples. These traits are traditionally measured by manually counting the fruits, weighing …
object-detectionObject DetectionObject LocalizationTheoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networks
Previous work has established that RNNs with an unbounded activation function have the capacity to count exactly. However, it has also been shown that RNNs are challenging to train effectively and generally do not learn …
A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers
Weighted first-order model counting (WFOMC) is a central task in lifted probabilistic inference: It asks for the weighted sum of all models of a first-order sentence over a finite domain. A long line of work has identifi…
Efficient Action Counting with Dynamic Queries
Temporal repetition counting aims to quantify the repeated action cycles within a video. The majority of existing methods rely on the similarity correlation matrix to characterize the repetitiveness of actions, but their…
Contrastive Learning