Algorithmic Graph Theory

Fall 2012

Tuesday, Thursday 12:00 noon - 1:30 pm, GHC 6002

Google Group: https://groups.google.com/d/forum/cmu-algorithmic-graph-theory

Instructor
Richard Peng
Office: Hillman 7713
E-mail: yangp -at- cs
Phone: (412) 992-0090

Description This is a 'reading course' that explores algorithmic graph theory by visiting some of the key problems and tools. The main goal is to systematically present essential tools in designing efficient algorithms. Most of the key techniques from these algorithms have already found applications in optimization, machine learning and statistics.

Announcements

Oct 22: Problem Set 3 has been posted, tentativelly it will be discussed during the meeting on Thursday, Nov 8.
Sep 30: Problem Set 2 has been posted, tentativelly it will be discussed during the meeting on Thursday, Oct 18.
Sep 24: The meeting originally scheduled on Wednesday September 26 is cancelled.
Sep 24: Meeting times and locations have been changed to Tuesdays and Thursdays from 12:00noon to 1:30pm in GHC 6002.
Sep 16: 5 more problems have been added to Problem Set 1.
Sep 7: Problem Set 1 has been posted, tentativelly it will be discussed during the meeting on Monday, Sep 24.

Schedule

Mon Sep 10	Introduction, Boruvka's algorithm for minimum spanning trees, Dijkstra's algorithm for shortest path
Wed Sep 12	depth-first search, strongly connected components, linear time algorithm for 2-SAT and testing triconnectivity
Mon Sep 17	Maximum Matching	Readings: Paths, Trees and Flowers
Wed Sep 19	Tutte-Berge theorem, Bipartite Matching in O(mn^1/2) Time, Maximum Flow and Minimum Cut	Readings: (approximate) maxflow in O(m^3/2) and O(m^4/3) Time.
Mon Sep 24	Problem Set 1	Readings: slides on minmum diameter spanning trees
Wed Sep 26	NO MEETING
Tue Oct 2	Algorithms on Trees
Thu Oct 4	Low Stretch Spanning Trees
Tue Oct 9	Mincost Branchings and Matroid Intersection
Thu Oct 11	Tree Packings
Tue Oct 16	Lexicographical BFS	Readings: Simpler approach using maximum cardinality search
Thu Oct 18	Problem Set 2
Tue Oct 23	Divide-and-Conquer Data Structures for Paths, Trees and more
Thu Oct 25	Link-cut trees
Tue Oct 30	Finding Blocking Flows in O(mlogn) Time
Thu Nov 1	k-th Shortest Path in O((m + k)logn) Time
Tue Nov 6	Multiple Source Shortest Path on Planar Graphs
Thu Nov 8	Problem Set 3
Tue Nov 13	Randomized O(n²m) algorithm for global mincut
Thu Nov 15	O(m) time randomized algorithm for finding minimum spanning trees	Simplified proof of sampling lemma
Tue Nov 20	Global mincut in nearly-linear time
Tue Nov 27	O(mn^1/2logU) time algorithm for negative length shortest path
Tue Nov 27	O(m^3/2logU) time algorithm for maxflow
Tue Nov 27	Maxflow Continued
Tue Nov 27	Ball Growing and Graph Partitioning

Evaluation Scheme Evaluation will be done via. problem sets. For each problem set, there is one meeting for discussing the questions that begins with everyone declaring the problems that they solved. Then for each problem one person who declared it will be asked to present its solution. Your final score will be the total number of problems declared multiplied by the fractional score on the problems presented. The number of problem sets (tentatively 4) will be adjusted based on attendance.