Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms

DOI10.1007/978-3-031-18530-4_15zbMath1528.90233MaRDI QIDQ6111508

Cheng-Chia Tseng, Jou-Ming Chang, Ling-Ju Hung, Ro-Yu Wu

Publication date: 3 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

spanning treesfan graphsconstant amortized time algorithmsgeneration algorithms ranking/unranking algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Ranking and unranking of non-regular trees with a prescribed branching sequence
• Spanning trees and function classes
• A flexible algorithm for generating all the spanning trees in undirected graphs
• An algorithm for enumerating all spanning trees of a directed graph
• A loopless algorithm for generating \((k, m)\)-ary trees in gray-code order
• Rank and select revisited and extended
• Optimal lower bounds for rank and select indexes
• A pivot Gray code listing for the spanning trees of the fan graph
• A CLASS OF GRAPHS WHICH HAS EFFICIENT RANKING AND UNRANKING ALGORITHMS FOR SPANNING TREES AND FORESTS
• Finding All Spanning Trees of Directed and Undirected Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Listing all spanning trees in Halin graphs — sequential and Parallel view
• Unranking and ranking spanning trees of a graph
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Two Algorithms for Unranking Arborescences

This page was built for publication: Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms