A CLASS OF GRAPHS WHICH HAS EFFICIENT RANKING AND UNRANKING ALGORITHMS FOR SPANNING TREES AND FORESTS

DOI10.1142/S0129054104002650zbMath1067.05030OpenAlexW2037056168MaRDI QIDQ3022025

Ömer Eğecioğlu, S. Gill Williamson, Jeffery B. Remmel

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054104002650

zbMATH Keywords

rankingenumerationcomplete bipartite graphspanning treeunrankingspanning forestcombinatorial generationfiltered digraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

The combinatorics of Jeff Remmel, Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms

Cites Work

• Bijections for Cayley trees, spanning trees, and their q-analogues
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Unranking and ranking spanning trees of a graph
• Unnamed Item
• Unnamed Item