Bounds on Sweep-Covers by Functional Compositions of Ordered Integer Partitions and Raney Numbers
share
A sweep-cover is a vertex separator in trees that covers all the nodes by some ancestor-descendent relationship. This work provides an algorithm for finding all sweep-covers of a given size in any tree. The algorithm's complexity is proven on a class of infinite Δ-ary trees with constant path lengths between the Δ-star internal nodes. I prove the enumeration expression on these infinite trees is a recurrence relation of functional compositions on ordered integer partitions. The upper bound on the enumeration is analyzed with respect to the size of sweep cover n, maximum out-degree Δ of the tree, and path length γ, O(n^n), O(Δ^c c^Δ), and O(γ ^n) respectively. I prove that the Raney numbers are a strict lower bound for enumerating sweep-covers on infinite Δ-ary trees, Ω((Δ n)^n/n!).
READ FULL TEXT