gotchaMinor
Spanning tree - minimum difference between smallest and largest weight
Viewed 0 times
smallestminimumweightlargestdifferencebetweenandspanningtree
Problem
I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the smallest possible.
I know how to find a minimal spanning tree, e.g. using Prim's algorithm or Kruskal's algorithm, but I don't know how to find a tree satisfying the above condition. Is it enough to modify the MST algorithm in some way? Anyone have an idea how to approach this?
I know how to find a minimal spanning tree, e.g. using Prim's algorithm or Kruskal's algorithm, but I don't know how to find a tree satisfying the above condition. Is it enough to modify the MST algorithm in some way? Anyone have an idea how to approach this?
Solution
You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed).
Let $e_1, e_2, \dots, e_m$ be the edges in the input graph $G$ in increasing order of weight. Define $G_i$ as the subgraph of $G$ induced by $\{e_i, \dots, e_m\}$, and let $k$ be the largest integer such that $G_k$ spans $G$.
For every $i=1,\dots,k$ let $T_i$ be a MST of $G_i$ and call $M_i$ the weight of the maximum-weight edge in $T_i$. The problem is equivalent to returning a tree $T_i$ minimizing $M_i - w_i$, where $w_i$ is the weight of $e_i$ (notice that $T_i$ must include $e_i$).
This is because a MST minimizes the maximum-weight of the selected edges.
As a consequence of the above discussion, we can focus on finding the trees $T_i$. We compute $T_k$ explicitly and then, for $i=k-1, k-2, \dots, 1$ we find $T_i$ by updating $T_{i+1}$ as follows:
Notice that it is possible to maintain a tree under edge insertions, deletions, and bottleneck queries in $O(\log n)$ amortized time per operation.
Similarly, we can keep the maximum edge weight in $T_i$ updated in $O(\log n)$ time per iteration by storing the weights of the selected edges in a heap.
Overall the time spent is $O(m \log n)$, which also accounts for the time needed to sort the edges of $G$ and to find $T_k$.
Let $e_1, e_2, \dots, e_m$ be the edges in the input graph $G$ in increasing order of weight. Define $G_i$ as the subgraph of $G$ induced by $\{e_i, \dots, e_m\}$, and let $k$ be the largest integer such that $G_k$ spans $G$.
For every $i=1,\dots,k$ let $T_i$ be a MST of $G_i$ and call $M_i$ the weight of the maximum-weight edge in $T_i$. The problem is equivalent to returning a tree $T_i$ minimizing $M_i - w_i$, where $w_i$ is the weight of $e_i$ (notice that $T_i$ must include $e_i$).
This is because a MST minimizes the maximum-weight of the selected edges.
As a consequence of the above discussion, we can focus on finding the trees $T_i$. We compute $T_k$ explicitly and then, for $i=k-1, k-2, \dots, 1$ we find $T_i$ by updating $T_{i+1}$ as follows:
- Find the bottleneck edge $f_i$ in the unique path $P_i$ between the endvertices of $e_i$ in $T_{i+1}$, i.e., the edge of maximum weight in $P_i$.
- Let $T_{i}$ be the tree obtained from $T_{i+1}$ by replacing $f$ with $e_i$.
Notice that it is possible to maintain a tree under edge insertions, deletions, and bottleneck queries in $O(\log n)$ amortized time per operation.
Similarly, we can keep the maximum edge weight in $T_i$ updated in $O(\log n)$ time per iteration by storing the weights of the selected edges in a heap.
Overall the time spent is $O(m \log n)$, which also accounts for the time needed to sort the edges of $G$ and to find $T_k$.
Context
StackExchange Computer Science Q#151803, answer score: 4
Revisions (0)
No revisions yet.