Abstract | : | We will discuss an interesting notion of greedy tree packaging introduced by Karger in STOC 96 with applications in finding cuts in graphs. The idea, quite simply put, is to construct a number of trees greedily and give guarantees with respect to the min cut and the edges in the greedy trees constructed. Thorup et al. in STOC 01 improved the analysis and showed that if there are a specific number of greedy trees constructed then one of them passes through a min-cut only once. In this talk, we will introduce tree packaging and discuss the important Chernoff bound style technique of pessimistic estimation used for the analysis. We will also give the use cases of tree packaging in dynamic connectivity [Thorup et al., STOC 01], minimum k-way connectivity [Thorup et al., STOC 08] and distributed connectivity [Nanongkai et al., DISC 14]. |