Gavril, Fănică Generating the maximum spanning trees of a weighted graph. (English) Zbl 0636.68091 J. Algorithms 8, 592-597 (1987). The present paper contains an efficient algorithm for generating all the maximum spanning trees of a weighted graph and a polynomial time algorithm for counting them. As known, the tree representations of an acyclic hypergraph are exactly the maximum spanning trees of the weighted intersection graph of its edges. Therefore, they can be generated and counted by these algorithms. Cited in 9 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05-04 Software, source code, etc. for problems pertaining to combinatorics 05C65 Hypergraphs Keywords:efficient algorithm; maximum spanning trees; weighted graph; polynomial time algorithm; tree representations; acyclic hypergraph PDFBibTeX XMLCite \textit{F. Gavril}, J. Algorithms 8, 592--597 (1987; Zbl 0636.68091) Full Text: DOI