Efficient generation of spanning arborescences with minimal edge changes
Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time
Data Structures and Algorithms
Summary
The paper addresses how to list all possible spanning arborescences—special directed trees—in certain types of directed graphs so that moving from one tree to the next requires only changing one edge. The authors develop the first known fast method that does this for complete digraphs, split digraphs, and certain interval digraphs. Their approach uses a clever recursive algorithm that runs quickly and uses reasonable memory. This means it’s possible to explore these structures one by one with minimal changes between them.
What this means in practice
- •For graph algorithm engineers: Generate all spanning arborescences of complete or split digraphs efficiently with minimal edge changes for testing and optimization purposes.
- •For network designers: Systematically explore network routing trees that differ by one assignment to evaluate and improve fault tolerance or adaptation.
Authors
Bowie Liu, Dennis Wong
Abstract
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.