The Blossom Algorithm

An overview of the Blossom algorithm for maximum graph matching.

------------------

Timetable:
0:00 - Introduction
0:41 - Definitions
1:02 - Augmenting paths
1:42 - Maximum tree matching
3:06 - Blossoms
4:06 - Maximum general graph matching
4:59 - Overview
5:46 - Outro

------------------

Source code:
https://github.com/xiaoxiae/videos/tr...

Music:
Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/trac...

Software used:
Manim (animations): https://github.com/ManimCommunity/manim/
Kdenlive (video): https://kdenlive.org/en/
ffmpeg (video): https://ffmpeg.org/
Vector Magic (images): https://vectormagic.com/
arecord (audio): https://linux.die.net/man/1/arecord
sox (audio): http://sox.sourceforge.net/

Social media:
Website (for other things I'm up to): https://slama.dev/
Patreon (if you'd like to support me): Patreon: YTomS

------------------

[EN] Proofs: https://web.stanford.edu/~rezab/class...
- graph has an a.p. if and only if the matching is not maximum: theorem 2.4
- graph has an a.p. if and only if compressed graph has an a.p.: theorem 2.9

[CZ] My notes on Martin Koutecký's Combinatorics and Graphs lecture:
https://slama.dev/lecture-notes/kombi...

[EN] Sketchy Notes on Edmonds’ Incredible Shrinking Blossom
http://www.cs.dartmouth.edu/~ac/Teach...

[EN] Amy Shoemaker and Sagar Vare's report on the blossom algorithm:
https://web.stanford.edu/~rezab/class...

[EN] Blossom algorithm on Wikipedia:
https://en.wikipedia.org/wiki/Blossom...