pipette
ESEspañol

Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time

Bowie Liu, Dennis Wong

PreprintClaims a big step

In the authors' words

We present the first known efficient algorithm to generate pivot Gray codes for spanning arborescences of complete digraphs, listing all spanning arborescences such that consecutive arborescences differ by reassigning the outgoing edge of exactly one vertex. Our recursive algorithm generates each spanning arborescence in constant amortized time using space. We then extend our algorithm to generate the first known pivot Gray codes for spanning arborescences of split digraphs, achieving constant amortized time per arborescence using space. Finally, we further generalize our approach to proper interval digraphs. When the arborescences are rooted at the leftmost interval, our algorithm generates the pivot Gray code in constant amortized time per arborescence using space.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.