Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time
En palabras de los autores
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.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.