Factoring a Permutation on a Broom

Abstract

A tree $T$ consisting of a line with edges $\{(1,2),(2,3),\dots ,(n-1,n)\}$ and with edges $\{(1,a_1),(1,a_2),\dots ,(1,a_k)\}$ (a star) attached on the left, is called a broom.
The edges of the tree $T$ are called $T$-transpositions. We give an algorithm to factor any permutation $\sigma$ of $\{a_1,a_2,\dots ,a_k,1,2,\dots ,n\}$ as a product of $T$-transpositions, and prove that the factorization produced by the algorithm has minimal length.