Parametric minimum spanning tree

Question

I look for a simple algorithm for parametric minimum spanning tree where the weight of the edge e is $a_e + \lambda b_e $. Can we simplify the algorithm in case $b_e=1$ for all edges?

Answer 1

I don't know of any "simple" algorithms, but algorithms are known. See for example Using Sparsification for Parametric Minimum Spanning Tree Problems or Parametric and Kinetic Minimum Spanning Trees.

If we assume $b_e = 1$ for all edges, then the situation does simplify. In this case it is just the usual minimum spanning tree problem with weights $a_e$ only. For a graph with $n$ vertices any spanning tree will have exactly $n-1$ edges. So, for any $\lambda \in \mathbb{R}$ the weight of any spanning tree $T$ is $\mathrm{wt}\, T = \sum_{e \in T} a_e + (n-1)\lambda$. It follows for any $\lambda \in \mathbb{R}$ the minimum spanning tree is just the minimum spanning tree gotten by weighting all edges with the weights $a_e$.