Algorithms Seminar/Spring10
From ResearchWiki
(Difference between revisions)
(→Schedule) |
(→Schedule) |
||
| Line 51: | Line 51: | ||
| Mar 31 || Planarity Testing || [http://www.cs.brown.edu/~rt/gdhandbook/chapters/planarity.pdf Planarity Testing and Embedding notes], [http://portal.acm.org/citation.cfm?id=321852 The seminal Hopcroft-Tarjan paper], State-of-the-art: [http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf Simplified O(n) Planarity by Edge Addition] and [http://hal.archives-ouvertes.fr/docs/00/09/78/36/PDF/Planarity0.pdf Tremaux trees and planarity] || Piyush | | Mar 31 || Planarity Testing || [http://www.cs.brown.edu/~rt/gdhandbook/chapters/planarity.pdf Planarity Testing and Embedding notes], [http://portal.acm.org/citation.cfm?id=321852 The seminal Hopcroft-Tarjan paper], State-of-the-art: [http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf Simplified O(n) Planarity by Edge Addition] and [http://hal.archives-ouvertes.fr/docs/00/09/78/36/PDF/Planarity0.pdf Tremaux trees and planarity] || Piyush | ||
|- | |- | ||
| - | | Apr 7 || Randomized linear time MST || [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf Section 7 in this paper] || Raj | + | | Apr 7 || Randomized linear time MST || [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf Section 7 in this paper], and [http://doi.acm.org/10.1145/201019.201022 the original Karger/Klein/Tarjan paper] || Raj |
|- | |- | ||
| Apr 14 || [http://reference.kfupm.edu.sa/content/o/n/on_the_all_pairs_shortest_path_problem_59456.pdf All pairs-shortest paths] || || JT | | Apr 14 || [http://reference.kfupm.edu.sa/content/o/n/on_the_all_pairs_shortest_path_problem_59456.pdf All pairs-shortest paths] || || JT | ||
Revision as of 04:53, 7 April 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, PhD 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. 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 connectivity | Dan 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 | All pairs-shortest paths | JT | |
| Apr 21 | Brian M | ||
| 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
- Hot off the presses: Evasiveness and the Distribution of Prime Numbers
