Algorithms Seminar/Spring10

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→Schedule)
 
(21 intermediate revisions not shown)
Line 17: Line 17:
* [http://www.cs.utah.edu/~huangrh Ruihong Huang], 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
* [mailto:jiang@cs.utah.edu Jiarong Jiang], PhD Student, School of Computing
-
* [http://www.jtolds.com/ JT Olds], MS 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
* [mailto:seth@cs.utah.edu Seth Juarez], PhD Student, School of Computing
Line 31: Line 31:
| 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
| 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://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 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|| || Jiarong
+
| 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|| || Jags
+
| 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|| || Seth
+
| 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 || || John
+
| 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'''  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Graph Algorithms'''  
|-
|-
-
| Mar 31 || Planarity Testing  || ||
+
| 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 || ||  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://www.cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf 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 <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'''  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Evasiveness: Graphs meet topology'''  

Latest revision as of 18:19, 21 April 2010

Topics in Graph Algorithms

Wed 3:40-5:00 MEB 3105


Participants

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 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


Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/Algorithms_Seminar/Spring10"
Personal tools