Algorithms Seminar/Spring10
From ResearchWiki
(Difference between revisions)
(→Schedule) |
(→Schedule) |
||
| (48 intermediate revisions not shown) | |||
| Line 4: | Line 4: | ||
'''MEB 3105''' | '''MEB 3105''' | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
==Participants== | ==Participants== | ||
| Line 33: | Line 15: | ||
* [mailto:jags@cs.utah.edu Jagadeesh Jagarlamudi], PhD Student, School of Computing | * [mailto:jags@cs.utah.edu Jagadeesh Jagarlamudi], PhD Student, School of Computing | ||
* [http://www.cs.utah.edu/~piyush Piyush Rai], PhD Student, School of Computing | * [http://www.cs.utah.edu/~piyush Piyush Rai], PhD Student, School of Computing | ||
| + | * [http://www.cs.utah.edu/~huangrh Ruihong Huang], PhD Student, School of Computing | ||
| + | * [mailto:jiang@cs.utah.edu Jiarong Jiang], PhD Student, School of Computing | ||
| + | * [http://www.jtolds.com/ JT Olds], PhD Student, School of Computing | ||
| + | * [mailto:seth@cs.utah.edu Seth Juarez], PhD Student, School of Computing | ||
==Schedule== | ==Schedule== | ||
| Line 41: | Line 27: | ||
| 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 | + | | 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 | + | | Jan 27 || Applications of Separators: The MIS problem || [ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/77/628/CS-TR-77-628.pdf Lipton-Tarjan], [http://faculty.cs.tamu.edu/chen/courses/cpsc669/s2003/project/baker.pdf Baker]|| JT |
|- | |- | ||
| - | | Feb 3 || Treewidth: defns, results, applications|| [http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/treewidth.pdf Erickson notes]|| Parasaran | + | | Feb 3 || Treewidth: defns, results, applications|| [http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/treewidth.pdf Erickson notes]. Also read Shiva Kintali's recent [http://kintali.wordpress.com/2010/01/28/approximating-treewidth/ blog post]. [http://www.cs.uu.nl/research/techreps/repo/CS-1992/1992-27.pdf Bodlaender'96]|| Parasaran |
|- | |- | ||
| - | | Feb 10 || Minors. well-quasi orders, kruskal, wagner, robertson-seymour. || [http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/graph-minors.pdf Erickson notes]|| Suresh | + | | Feb 10 || Minors. well-quasi orders, kruskal, wagner, robertson-seymour. || [http://en.wikipedia.org/wiki/Well-quasi-ordering well-quasi orders], [http://www.google.com/url?sa=t&source=web&ct=res&cd=15&ved=0CCAQFjAEOAo&url=ftp%3A%2F%2Fftp.cis.upenn.edu%2Fpub%2Fpapers%2Fgallier%2Fkruskal1.ps&ei=h6VQS5P2JYf8tQO44c32Bw&usg=AFQjCNHqsIMWSZrggRSBdOPHY-tH_QncsQ&sig2=X0fWrAhen16BpJo7nVRqww Higman's lemma (Section 3)], [http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem Kruskal's theorem], [http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/graph-minors.pdf Erickson notes]|| Suresh |
|- | |- | ||
| - | | Feb 17 || Diameter-treewidth: graphs of bounded treewidth exclude planar graphs. bidimensionality.|| || Ruihong | + | | Feb 17 || Diameter-treewidth: graphs of bounded treewidth exclude planar graphs. bidimensionality.|| [http://www.cs.utah.edu/~suresh/seminar/spring10/diam-treewidth/notes.pdf My notes], [http://www.cs.utah.edu/~suresh/seminar/spring10/diam-treewidth/bidim-ptas.pdf Demaine/Hajighayi paper] on bidimensionality for approximations (only Section 4) || Ruihong |
|- | |- | ||
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Spectral Graph Theory''' | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Spectral Graph Theory''' | ||
|- | |- | ||
| - | | Feb 24 || Spectral properties of graphs: Laplacian and connectivity|| || | + | | Feb 24 || Spectral properties of graphs: Laplacian and connectivity||Dan Spielman's lecture notes, [http://www.cs.yale.edu/homes/spielman/561/lect02-09.pdf part I] and [http://www.cs.yale.edu/homes/spielman/561/lect03-09.pdf part II] || Jiarong |
|- | |- | ||
| - | | Mar 3 || Second eigenvalue and cuts. Cheeger's inequality|| || | + | | Mar 3 || Second eigenvalue and cuts. Cheeger's inequality|| Dan Spielman's lecture notes ([http://www.cs.yale.edu/homes/spielman/561/lect05-09.pdf part I] (for the importance of the second eigenvalue of L, and [http://www.cs.yale.edu/homes/spielman/561/lect07-09.pdf part II], for Cheeger's inequality)|| Jags |
|- | |- | ||
| - | | Mar 10 || Separators via spectral properties|| || | + | | Mar 10 || Separators via spectral properties|| [http://tcsmath.wordpress.com/2008/10/08/lecture-4-conformal-mappings-circle-packings-and-spectral-geometry/ James Lee outline], [http://www.cs.yale.edu/homes/spielman/course/lect3.ps Dan Spielman notes on Koebe theorem], [http://www.cs.washington.edu/homes/jrl/tocmath08/st.pdf main Spielman-Teng paper] (only the first four sections) || Seth |
|- | |- | ||
| - | | Mar 17 || Spectral Sparsification || || | + | | Mar 17 || Spectral Sparsification || [http://arxiv.org/PS_cache/arxiv/pdf/0803/0803.0929v4.pdf Srivastava/Spielman paper on spectral sparsification], [http://www.cs.yale.edu/homes/srivastava/papers/sparse-talk.pdf Nikhil Srivastava's slides] || John |
|- | |- | ||
| - | | | + | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Graph Algorithms''' |
|- | |- | ||
| - | | | + | | 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 14 || || || | + | | Apr 7 || Randomized linear time MST || [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf Section 7 in this paper], and [http://www.cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf the original Karger/Klein/Tarjan paper] || Raj |
| + | |- | ||
| + | | Apr <strike>14</strike> 16 (in Graphics Annex) || Shortest Paths || [http://reference.kfupm.edu.sa/content/o/n/on_the_all_pairs_shortest_path_problem_59456.pdf On the all-pairs shortest path problem]|| JT | ||
|- | |- | ||
| - | | Apr 21 || || || | + | | Apr <strike>21</strike> '''23 (in LCR)''' || Dynamic Graph Algorithms || [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8372 Survey] (focus on the min spanning forest problem - parts of Sec 4 and 5) and sparsification) || Brian M |
| + | |- | ||
| + | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Evasiveness: Graphs meet topology''' | ||
|- | |- | ||
| Apr 28 || || || | | Apr 28 || || || | ||
| Line 78: | Line 68: | ||
* [http://www2.informatik.hu-berlin.de/~grohe/pub/gro03b.pdf Local treewidth and approximations] | * [http://www2.informatik.hu-berlin.de/~grohe/pub/gro03b.pdf Local treewidth and approximations] | ||
* [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] | ||
| + | |||
| + | |||
| + | * 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 | ||
| + | ** '''Hot off the presses''': [http://arxiv.org/abs/1001.4829 Evasiveness and the Distribution of Prime Numbers] | ||
Latest revision as of 18:19, 21 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 | Shortest Paths | On the all-pairs shortest path problem | JT |
| Apr | 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
- 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
