2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.