Using sparsification for parametric minimum spanning tree problems
David Fernández‐Baca, Giora Slutzki, David Eppstein · 1996
. Two applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parameter. The second is an asymptotically optimal algorithm for the minimum ratio spanning tree problem, as well as other search problems, on dense graphs. 1 Introduction In the parametric minimum spanning tree problem, one is given an n-node, m-edge undirected graph G where each edge e has a linear weight function w e () = a e + b e . Let Z() denote the weight of the minimum spanning tree relative to the weights w e (). It can be shown that Z() is a piecewise linear concave function of [Gus80]; the points at which the slope of Z changes are called breakpoints. We shall present two results regarding parametric minimum spanning trees. First, we show that Z() can be constructed in O(minfnm log n; TMST (2n; n) \\Delta b(m; n)g) time, where TMST (m; n) is the time to compute a mi...