2010/09/10 by Jeffrey B. Remmel, Remmel, Jeffrey B., S. Gill Williamson +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods #math.CO
paper · pdf · doi:10.48550/arxiv.1009.2060
arxiv created 2010/09/10 · openalex publication_date 2010/09/10 · arxiv updated 2010/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we provide algorithms to rank and unrank certain degree-restricted classes of Cayley trees (spanning trees of the n-vertex complete graph). Specifically, we consider classes of trees that have a given set of leaves or a fixed number k of leaves. For fixed k, the number of Cayley trees with n vertices and k leaves grows roughly as n! and hence the ranks have O(nlog2(n)) bits. Our ranking and unranking algorithms require at most O(n2) comparisons of numbers less than or equal to n plus O(n) operations of multiplication, division, addition, substraction and comparision on numbers of length O(nlog(n)).