Algorithms on Digraphs

Advanced Course 2+1

Basic Information

Given by:Saeed Amiri and Will Rosenbaum (Featured guest lecture given by Eunjin Oh), TA: Eunjin Oh.
Time:

Monday 10:00- 12:00, TA session (initial setting): Wednesday 16:00-18:00

Room:024
First Meeting:October 22th. 
Credits:5 credit points
Grade formula:

50% final exam + 50 % exercises (25% solutions to the homework and 25 percent productive appearance in the exercise sessions)

Prerequisites:

The course will assume a basic background in graph theory and the analysis of algorithms, but we will not presume any specific experience with directed graphs.

News

Description

Algorithmic graph theory is one of the oldest and best-studied subjects in computer science. The classical theory assumes edges, i.e., connections between nodes, are symmetric: if there is an edge connecting $v$ to $u$, then the same edge connects $u$ to $v$. However, in many physical systems, connections are inherently asymmetric. Such systems are best modeled by directed graphs (digraphs). Unfortunately, many problems that are straightforward to solve for undirected graphs become difficult or intractible for digraphs. In many cases, methods for dealing with digraphs are intrinsically different from the corresponding methods for undirected graphs.

In this course we will cover some recently developed techniques for designing algorithms on digraphs. We will focus on three main topics:

1. Separators and cuts, with applications to the feedback vertex set and multiway cut problems.

2. Routing problems such as the disjoint paths problem, finding long paths, and packet scheduling and routing.

3. Structural properties of digraphs, in particular directed treewidth.

Additionally, there will be guest lectures by Eunjin Oh, who will discuss related problems arising in computational geometry.

The course will assume a basic background in graph theory and the analysis of algorithms, but we will not presume any specific experience with directed graphs.

Mailing List

If you are interested in taking this course, please join our mailing list by clicking on this link.

Schedule

Moday 10-12 for main course and every second Wednesday 16-18 for the TA session. Final exam is an oral exam and we will announce the exam date later.

Papers