pipette
ENEnglish

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

Bowie Liu, Dennis Wong

PreprintDice ser un gran avance

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.