en
0.25
0.5
0.75
1.25
1.5
1.75
2
Randomized techniques for parameterized algorithms
Published on 2012-10-023580 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