Algorithms Seminar/Spring10

From ResearchWiki

Revision as of 03:37, 27 January 2010 (view source) Jtolds (Talk | contribs) (→Schedule) ← Older edit		Revision as of 06:34, 27 January 2010 (view source) Schizoid (Talk | contribs) (→Outline) Newer edit →
Line 4:		Line 4:
	'''MEB 3105'''		'''MEB 3105'''
-	==Outline==
-	* 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
	==Participants==		==Participants==

---

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