On the complexity of computing Strahler numbers

Moses Ganardi, Markus Lohrey

It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform ${\mathsf{NC}}^1$. For several var…