Camerini.27s algorithm for undirected graphs Minimum bottleneck spanning tree

1 camerini s algorithm undirected graphs

1.1 pseudocode
1.2 running time
1.3 example

camerini s algorithm undirected graphs

camerini proposed algorithm used obtain minimum bottleneck spanning tree (mbst) in given undirected, connected, edge-weighted graph in 1978. half divides edges 2 sets. weights of edges in 1 set no more in other. if spanning tree exists in subgraph composed solely edges in smaller edges set, computes mbst in subgraph, mbst of subgraph mbst of original graph. if spanning tree not exist, combines each disconnected component new super vertex, computes mbst in graph formed these super vertices , edges in larger edges set. forest in each disconnected component part of mbst in original graph. repeat process until 2 (super) vertices left in graph , single edge smallest weight between them added. mbst found consisting of edges found in previous steps.

pseudocode

the procedure has 2 input parameters. g graph, w weights array of edges in graph g.

1 function mbst(graph g, weights w)
2 e ← set of edges of g
3 if | e | = 1 return e else
4 ← half edges in e weights no less median weight
5 b ← e - a
6 f ← forest of gb
7 if f spanning tree then
8 return mbst(gb,w)
9 else
10 return mbst((ga)η, w)



∪


{\displaystyle \cup }

f

in above (ga)η subgraph composed of super vertices (by regarding vertices in disconnected component one) , edges in a.

running time

the algorithm running in o(e) time, e number of edges. bound achieved follows:

dividing 2 sets median-finding algorithms in o(e)
finding forest in o(e)
considering half edges in e in each iteration o(e + e/2 + e/4 + ··· + 1) = o(e)

example

in following example green edges used form mbst , dashed red areas indicate super vertices formed during algorithm steps.