Algorithms Seminar/Spring10

From ResearchWiki

Jump to: navigation, search

Topics in Graph Algorithms

Wed 3:40-5:00 MEB 3105



Date Topic Paper(s) Presenter
Planarity, Treewidth and Minors
Jan 13 Planar graphs and separators Lipton-Tarjan separator theorem, Gary Miller's cycle separator Suresh (notes)
Jan 27 Applications of Separators: The MIS problem Lipton-Tarjan, Baker JT
Feb 3 Treewidth: defns, results, applications Erickson notes. Also read Shiva Kintali's recent blog post. Bodlaender'96 Parasaran
Feb 10 Minors. well-quasi orders, kruskal, wagner, robertson-seymour. well-quasi orders, Higman's lemma (Section 3), Kruskal's theorem, Erickson notes Suresh
Feb 17 Diameter-treewidth: graphs of bounded treewidth exclude planar graphs. bidimensionality. My notes, Demaine/Hajighayi paper on bidimensionality for approximations (only Section 4) Ruihong
Spectral Graph Theory
Feb 24 Spectral properties of graphs: Laplacian and connectivityDan Spielman's lecture notes, part I and part II Jiarong
Mar 3 Second eigenvalue and cuts. Cheeger's inequality Dan Spielman's lecture notes (part I (for the importance of the second eigenvalue of L, and part II, for Cheeger's inequality) Jags
Mar 10 Separators via spectral properties James Lee outline, Dan Spielman notes on Koebe theorem, main Spielman-Teng paper (only the first four sections) Seth
Mar 17 Spectral Sparsification Srivastava/Spielman paper on spectral sparsification, Nikhil Srivastava's slides John
Graph Algorithms
Mar 31 Planarity Testing Planarity Testing and Embedding notes, The seminal Hopcroft-Tarjan paper, State-of-the-art: Simplified O(n) Planarity by Edge Addition and Tremaux trees and planarity Piyush
Apr 7 Randomized linear time MST Section 7 in this paper, and the original Karger/Klein/Tarjan paper Raj
Apr 14 16 (in Graphics Annex) Shortest Paths On the all-pairs shortest path problem JT
Apr 21 23 (in LCR) Dynamic Graph Algorithms Survey (focus on the min spanning forest problem - parts of Sec 4 and 5) and sparsification) Brian M
Evasiveness: Graphs meet topology
Apr 28
May 5?

Reading Dumplist

Personal tools