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