The Blossom Algorithm
39.8 هزار بار بازدید -
3 سال پیش
-
An overview of the Blossom
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...
------------------
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...
3 سال پیش
در تاریخ 1400/05/31 منتشر شده
است.
39,822
بـار بازدید شده