×

Generating the maximum spanning trees of a weighted graph. (English) Zbl 0636.68091

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.

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
PDFBibTeX XMLCite
Full Text: DOI