EngGuide

Algorithms Live! Episode 22 - Biconnected Decompositions

In this episode, I discuss how to solve problems using undirected graph information we learned to extract last week through the DFS lowlinking technique.

00:52 - Problem: make graph 2-edge-connected
15:10 - Using Euler tour to simplify pendant matching
19:54 - ICPC World Finals problem "Mining Your Own Business"
23:53 - Creating a tree of biconnected components
28:55 - Leveraging meta-tree to solve our problem
32:33 - Avoiding explicit construction of meta-tree
33:45 - "Lucky Cities" SEERC-ICPC problem
37:03 - Cycle lengths and bipartite graphs
39:11 - Proof: Every vertex of a non-bipartite 2-vertex-connected graph lies on an odd-cycle

Thank you to Mikhail Goncharov for the time links!