Pivot Gray codes for the spanning trees of a graph ft. the fan

DOI10.1007/S00373-024-02808-2MaRDI QIDQ6580496zbMATH OpenFDO

Authors Ben Cameron, Aaron Grubb, Joe Sawada

Publication date 29 July 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00373-024-02808-2

zbMATH Keywords

combinatorial generationfan graphgreedy algorithmpivot Gray codespanning tree

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial codes (94B25)

Recommendations

• Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms
• Combinatorial Gray codes -- an updated survey
• scientific article; zbMATH DE number 177570
• Generating binary trees by transpositions
• Gray code enumeration of plane straight-line graphs

Cites work

• A flexible algorithm for generating all the spanning trees in undirected graphs
• A pivot Gray code listing for the spanning trees of the fan graph
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• All your bases are belong to us: listing all bases of a matroid by greedy exchanges
• An algorithm for enumerating all spanning trees of a directed graph
• An algorithm for the enumeration of spanning trees
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Combinatorial generation via permutation languages
• Combinatorial generation via permutation languages. III: Rectangulations
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
• Fast enumeration algorithms for non-crossing geometric graphs
• Finding All Spanning Trees of Directed and Undirected Graphs
• Formulas for the number of spanning trees in a fan
• Gray code enumeration of plane straight-line graphs
• New bounds for matrix multiplication: from alpha to omega
• On the Tree Graph of a Matroid
• On trees of a graph and their generation
• Reverse search for enumeration
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The greedy Gray code algorithm
• Two Algorithms for Unranking Arborescences
• Über Stromverzweigung in netzförmigen Leitern.

Cited in

(3)

• Maximize the rightmost digit: Gray codes for restricted growth strings
• Listing spanning trees of outerplanar graphs by Pivot-exchanges
• On shortest path, \textsf{BFS}- and \textsf{DFS}-tree graphs

This page was built for publication: Pivot Gray codes for the spanning trees of a graph ft. the fan

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6580496)