arXiv:2610.37783 · v1

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

首次提交 2026-10-28 02:04

版本更新 2026-10-28 02:04

雷达观测 2026-10-30 10:23

摘要

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 $O(n^2)$ 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 $ O(n^2) $ 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 $ {O}(n^2) $ space.