1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ So what if graph $G$ has 3 Vertices $A,B,C$ with edge $w(AB)=1,w(BC)=3, w(e_m)=2$ So the algorithm now recurses on graph $G_2$ which has vertices $B,C$ - wont that just return an MST of $BC$, isn't there some kind of union or other operation that would need to happen with $G_1$? $\endgroup$ – Elliott de Launay Apr 11 at 14:21
  • 1
    $\begingroup$ First of all, $e_{m}$ is the median weighted edge. For example, if edge set is $\{ 1,1,1,1,100\}$ then the $w(e_{m}) = 1$ and not $52$. $\endgroup$ – Inuyasha Yagami Apr 11 at 14:24
  • 1
    $\begingroup$ Second, we are not recursing on $G_{2}$. $\endgroup$ – Inuyasha Yagami Apr 11 at 14:24
  • 1
    $\begingroup$ We are just finding the median of $G_{2}$. That median will partition the entire graph $G$ into new subgraphs $G_{1}'$ and $G_{2}'$. Here, $G_{1}'$ already contains older $G_{1}$. Therefore, no union operation is required. $\endgroup$ – Inuyasha Yagami Apr 11 at 14:25
  • $\begingroup$ Ah! Very good - thank you! $\endgroup$ – Elliott de Launay Apr 11 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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