6533b838fe1ef96bd12a3f14
RESEARCH PRODUCT
The pruning-grafting lattice of binary trees
Jean-luc BarilJean Marcel Pallosubject
General Computer ScienceMatching (graph theory)Distribution sequences0102 computer and information sciencesFeasible sequences01 natural sciencesTheoretical Computer ScienceCombinatoricsCatalan numbersymbols.namesakeLattice (order)[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0101 mathematicsComputingMilieux_MISCELLANEOUSMathematicsBinary tree010102 general mathematicsEulerian pathLatticesJoin (topology)Binary trees010201 computation theory & mathematicsShortest path problemPath (graph theory)symbolsCatalan numbersComputer Science(all)description
AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2008-12-01 |