Algorithms Seminar/Spring10
From ResearchWiki
(Difference between revisions)
(→Schedule) |
m (→Schedule) |
||
| Line 42: | Line 42: | ||
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Planarity, Treewidth and Minors''' | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Planarity, Treewidth and Minors''' | ||
|- | |- | ||
| - | | Jan 13 || Planar graphs and separators|| [http://infolab.stanford.edu/pub/cstr/reports/cs/tr/77/627/CS-TR-77-627.pdf Lipton-Tarjan separator theorem], [http://www-2.cs.cmu.edu/~glmiller/Publications/Papers/Mi87.pdf Gary Miller's cycle separator]|| Suresh [[Talk:Algorithms_Seminar/Spring10#Jan_13|notes]] | + | | Jan 13 || Planar graphs and separators|| [http://infolab.stanford.edu/pub/cstr/reports/cs/tr/77/627/CS-TR-77-627.pdf Lipton-Tarjan separator theorem], [http://www-2.cs.cmu.edu/~glmiller/Publications/Papers/Mi87.pdf Gary Miller's cycle separator]|| Suresh [[Talk:Algorithms_Seminar/Spring10#Jan_13|(notes)]] |
|- | |- | ||
| Jan 27 || Applications of Separators: MIS, Baker || || | | Jan 27 || Applications of Separators: MIS, Baker || || | ||
Revision as of 05:44, 13 January 2010
Topics in Graph Algorithms
Wed 3:40-5:00 MEB 3105
Contents |
Outline
- separator structures on graphs: planarity, treewidth, and the robertson-seymour theorem
- A tourist guide through treewidth
- Application: junction trees in graphical models (2.5.2)
- Application: solving NP-hard problems on graphs of bounded treewidth.
- General algorithmic methods for solving problems on graphs of bounded treewidth
- Nice survey of Courcelle's theorem and implications.
- separators for graphs with excluded minors
- Spectral properties of graphs
- laplacian and connectivity
- second eigenvalue and cuts. Cheeger's inequality
- Spielman/Teng spectral separator theorem and related notes:
- spectral sparsification
- evasiveness
Participants
- Suresh Venkatasubramanian, Assistant Professor, School of Computing
- Jeff Phillips, CI Postdoctoral Fellow, School of Computing
- Parasaran Raman, PhD Student, School of Computing
- Raj Varma Kommaraju, MS Student, School of Computing
- Avishek Saha, PhD Student, School of Computing
- John Moeller, PhD Student, School of Computing
- Jagadeesh Jagarlamudi, PhD Student, School of Computing
- Piyush Rai, PhD Student, School of Computing
- Ruihong Huang, PhD Student, School of Computing
Schedule
| 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: MIS, Baker | ||
| Feb 3 | Treewidth: defns, results, applications | Erickson notes | Parasaran |
| Feb 10 | Minors. well-quasi orders, kruskal, wagner, robertson-seymour. | Erickson notes | Suresh |
| Feb 17 | Diameter-treewidth: graphs of bounded treewidth exclude planar graphs. bidimensionality. | Ruihong | |
| Spectral Graph Theory | |||
| Feb 24 | Spectral properties of graphs: Laplacian and connectivity | ||
| Mar 3 | Second eigenvalue and cuts. Cheeger's inequality | ||
| Mar 10 | Separators via spectral properties | ||
| Mar 17 | Spectral Sparsification | ||
| Mar 31 | |||
| Apr 7 | |||
| Apr 14 | |||
| Apr 21 | |||
| Apr 28 | |||
| May 5? | |||
