Prune and search Algorithm for Generating a Bottleneck Spanning Tree I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G into two graphs containing the edges which are less than or equal to the median or greater than.
After separating the graphs, I test the median weight against the original graph (G) to see if it is a bottleneck value. I'm stuck on what to do, if the median is not a bottleneck value, I was thinking maybe I could compact the graph of edges with weights less than the median - but the cut of a compacted graph would still have the weights so the median wouldn't change. I'm thinking I need to form an MST at some point as well?
So far I have something like:
def F(G):
  m = find_avg_weight_of_edges(G)
  G_le_m = get_g_w_edge_weight_less_than_or_eqal_to(G,m)
  G_gt_m = get_g_w_edge_weight_greater_than(G,m)
  if is_bottleneck_value(G,x):
    T = F(G_le_m)
  else:
    # note quite sure what to do... 
    # I can't remove the less than or equal to edges 
    # since they are needed to make up the MST
    # but if I don't remove them m won't change
    # maybe some kind of reduce/scc function?
return T
Let $b$ is the bottleneck edge of $MBST$, and let $b$ has weight $w(b)$.
Suppose $e_{m}$ is the median weighted edge of $G$, and let $e_{m}$ has weight $w(e_{m})$. Suppose $G$ gets partitioned into two subgraphs $G_{1}$ and $G_{2}$ such that edges in $G_{1}$ have weight $\leq w(e_{m})$ and edges in $G_{2}$ have weight $&gt; w(e_{m})$.
If $w(b) \leq w(e_{m})$, then there must exist an $MBST$ within $G_{1}$ itself. Since the algorithm is recursing on $G_{1}$, it will output an $MBST$ if it exists. If the algorithm does not output a valid spanning tree, it means $b \notin G_{1}$. In other words, $b \in G_{2}$.
In that case, the algorithm will update $e_{m}$ to be the median weight edge of $G_{2}$. The graph $G$ will again get partitioned into two subgraphs $G_{1}$ and $G_{2}$. And, the algorithm can repeat this process.