Algorithms Seminar/Spring10
From ResearchWiki
(Difference between revisions)
(→Outline) |
(→Reading Dumplist) |
||
| Line 69: | Line 69: | ||
* [http://e-math1.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf Lovasz review of graph minor theory] | * [http://e-math1.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf Lovasz review of graph minor theory] | ||
* [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf MST survey] | * [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf MST survey] | ||
| + | |||
| + | |||
| + | * separator structures on graphs: planarity, treewidth, and the robertson-seymour theorem | ||
| + | ** [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] | ||
| + | ** An application: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.4667&rep=rep1&type=pdf linear time shortest paths for planar graphs] | ||
| + | ** Application: [http://historical.ncstrl.org/litesite-data/stan/CS-TR-77-628.pdf PTAS for finding maximum independent sets in planar graphs] | ||
| + | |||
| + | * [http://www.cs.uu.nl/research/techreps/repo/CS-1992/1992-12.pdf A tourist guide through treewidth] | ||
| + | ** Application: [http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf junction trees in graphical models (2.5.2)] | ||
| + | ** Application: solving NP-hard problems on graphs of bounded treewidth. | ||
| + | ** [http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1997/1997-31.ps.gz General algorithmic methods for solving problems on graphs of bounded treewidth] | ||
| + | ** [http://www.google.com/url?sa=t&source=web&ct=res&cd=24&ved=0CBkQFjADOBQ&url=http%3A%2F%2Fhomepages.ecs.vuw.ac.nz%2F~mathmeet%2Fnewplymouth%2Fnzm1.ps&ei=JDhES4CmJIn8tAOO6I0h&usg=AFQjCNFa4EbJPnSO4V8RTgJNexKe98rHQw&sig2=83aPogymDvnNN1QQA77I7w Nice survey of Courcelle's theorem and implications]. | ||
| + | * [http://www.cs.tau.ac.il/~nogaa/PDFS/spr.pdf separators for graphs with excluded minors] | ||
| + | * Spectral properties of graphs | ||
| + | ** laplacian and connectivity | ||
| + | ** second eigenvalue and cuts. Cheeger's inequality | ||
| + | ** [http://www.cs.yale.edu/homes/spielman/561/lect25-09.pdf Spielman/Teng spectral separator theorem] and [http://math.mit.edu/~spielman/course/lect3.html related notes]: | ||
| + | ** [http://arxiv.org/abs/0808.4134 spectral sparsification] | ||
| + | * evasiveness | ||
Revision as of 06:34, 27 January 2010
Topics in Graph Algorithms
Wed 3:40-5:00 MEB 3105
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
- Jiarong Jiang, PhD Student, School of Computing
- JT Olds, MS Student, School of Computing
- Seth Juarez, 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: The MIS problem | Lipton-Tarjan, Baker | JT |
| Feb 3 | Treewidth: defns, results, applications | Erickson notes | 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. | Ruihong | |
| Spectral Graph Theory | |||
| Feb 24 | Spectral properties of graphs: Laplacian and connectivity | Jiarong | |
| Mar 3 | Second eigenvalue and cuts. Cheeger's inequality | Jags | |
| Mar 10 | Separators via spectral properties | Seth | |
| Mar 17 | Spectral Sparsification | John | |
| Graph Algorithms | |||
| Mar 31 | Planarity Testing | ||
| Apr 7 | Randomized linear time MST | Raj | |
| Apr 14 | All pairs-shortest paths | JT | |
| Apr 21 | |||
| Evasiveness: Graphs meet topology | |||
| Apr 28 | |||
| May 5? | |||
Reading Dumplist
- On computing graph minor obstruction sets
- Local treewidth and approximations
- Lovasz review of graph minor theory
- MST survey
- 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
