Cherry reduction sequences and linear extensions
Presenter
October 22, 2024
Abstract
Orchard and tree-child networks can be completely reduced to a single node by cherry and reticulated-cherry reductions. In this talk we investigate the problem to counting these reductions. In particular, we show the connexion between computing this number and computing the number of linear extensions of the poset induced by the network. Finally, we provide an algorithm (adapted from others) to obtain this number and we emphasise that its complexity is bounded in terms of the level and the tree-width parameters of the network. This is a joint work with T. MartÃnez-Coronado and G. Riera.