Tutorials: Exploiting Graph Structure in Algorithms (April 24th - April 27th, 2014)

Please note that space is limited, so registration is required.

This set of tutorials will cover the many important techniques developed in recent years for fixed-parameter algorithms (finely characterizing algorithmic performance by parameters beyond the problem size), approximation algorithms (guaranteeing near-optimal solutions), graph classes (particularly minors and treewidth), lower-bound techniques, and applications to practical networks. The tutorials will assume only basic algorithmic knowledge (at the level of an introductory graduate algorithms class).

Short Tutorial Descriptions PDF

Thursday April 24th
Time Description
8:30 - 9:00Registration
9:00 - 10:20Basic techniques of fixed-parameter tractability (Part 1), Saket Saurabh, Institute of Mathematical Sciences
10:30 - 11:00Coffee/Tea Break
11:00 - 12:30Basic techniques of fixed-parameter tractability (Part 2), Daniel Lokshtanov, University of Bergen
12:30 - 2:00Break for Lunch & Free Time
2:00 - 3:30Kernelization, Saket Saurabh, Institute of Mathematical Sciences
3:30 - 4:00Coffee/Tea Break
FridayApril 25th
Time Description
9:00 - 10:20Treewidth and applications, Fedor Fomin, University of Bergen
10:30 - 10:45Coffee/Tea Break
10:45 - 11:15Open Problem Session
11:15 - 12:45Minors & Algorithms , Erik Demaine, MIT
SaturdayApril 26th
Time Description
9:00 - 10:20Approximation Algorithms, MohammedTaghi Hajiaghayi, University of Maryland
10:30 - 11:00Coffee/Tea Break
11:00 - 12:30Lower bounds, Daniel Marx, Hungarian Academy of Sciences
SundayApril 27th
Time Description
9:00 - 10:20Separators, Daniel Marx, Hungarian Academy of Sciences
10:30 - 11:00Coffee/Tea Break
11:00 - 12:30Connecting to the Real-World/Applications, Blair Sullivan, North Carolina State University