A Stronger Lower Bound on Parametric Minimum Spanning Trees
share
We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter λ, the number of different minimum spanning trees obtained as the parameter varies can be Ω(mlog n).
READ FULL TEXT