P47: Enumeration of the $k$ best spanning trees in a graph

P47: Enumeration of the $k$ best spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best spanning trees of $G$.

Complexity:

$O(m\log\beta(|E|, |V|) + k^2)$ total time.

Comment:

$\beta(|E|, |V|) = \min \{\log^{(i)}|V| \le |E|/|V|\}$.

Reference:

[Eppstein1992] (Bibtex)