en
0.25
0.5
0.75
1.25
1.5
1.75
2
Randomized techniques for parameterized algorithms
Published on Feb 4, 20253572 Views
Since the introduction of the Color Coding technique in 1994 by Alon, Yuster, and Zwick, randomization has been part of the toolkit for proving fixed-parameter tractability results. It seems that ra
Related categories
Presentation
Randomized techniques for parameterized algorithms00:00
Why randomized?00:00
Polynomial time vs. FPT (1)01:21
Polynomial time vs. FPT (2)02:36
Randomization04:47
Randomization as reduction05:26
Color Coding (1)06:08
Color Coding (2)07:42
Color Coding (3)07:52
Color Coding (4)07:57
Error probability (1)09:10
Error probability (2)09:35
Finding a path colored 1 - 2 -... - k (1)10:24
Finding a path colored 1 - 2 -... - k (2)10:33
Finding a path colored 1 - 2 -... - k (3)10:42
Finding a path colored 1 - 2 -... - k (4)10:44
Finding a path colored 1 - 2 -... - k (5)10:51
Color Coding10:56
Improved Color Coding (1)11:26
Improved Color Coding (2)11:43
Improved Color Coding (3)12:05
Finding a colorful path12:27
Improved Color Coding12:58
Derandomization (1)13:22
Derandomization (2)14:37
Derandomized Color Coding15:03
Bounded-degree graphs15:55
Dense k-vertex Subgraph (1)17:22
Dense k-vertex Subgraph (2)17:47
Dense k-vertex Subgraph (3)18:20
Dense k-vertex Subgraph (4)19:01
Dense k-vertex Subgraph (5)19:20
Dense k-vertex Subgraph (6)19:45
Balanced Separation (1)20:36
Balanced Separation (2)21:06
Balanced Separation (3)21:22
Balanced Separation (4)21:37
Balanced Separation (5)22:06
Balanced Separation (6)22:51
Randomized sampling of important separators23:06
Transversal problems24:15
The setting (1)26:00
The setting (2)27:01
The random sampling (undirected edge version)27:12
Clustering29:12
A sufficient and necessary condition (1)30:25
A sufficient and necessary condition (2)30:41
A sufficient and necessary condition (3)30:59
A sufficient and necessary condition (4)31:15
A sufficient and necessary condition (5)31:38
A sufficient and necessary condition (6)32:03
Finding a good cluster (1)32:21
Finding a good cluster (2)32:38
Random sampling (repeated)33:07
Finding good clusters (1)34:03
Finding good clusters (2)35:11
Finding good clusters (3)36:01
(p; q)-clustering36:37
Multiway cut37:09
Directed Multiway Cut38:03
The random sampling (directed vertex version)38:53
Shadow removal (1)40:14
Shadow removal (2)40:38
Shadow removal (3)40:46
Shadow removal (4)41:05
Shadowless solutions (1)41:50
Shadowless solutions (2)42:03
Shadowless solutions (3)43:17
Cut and count (1)43:54
Isolation Lemma (1)46:48
Isolation Lemma (2)48:04
Cycle covers (1)49:03
Cycle covers (2)49:20
Cycle covers (3)49:33
Cycle covers (4)50:03
Cycle covers (5)50:08
Cycle covers (6)50:24
Cycle covers (7)51:28
Cut and Count (2)51:32
Cut and Count (3)53:11
Conclusions53:43