Algorithms Seminar/Spring10

From ResearchWiki

Topics in Graph Algorithms

Wed 1:25-2:45 WEB 1460

Outline

• separator structures on graphs: planarity, treewidth, and the robertson-seymour theorem
  • Lipton-Tarjan separator theorem
  • Gary Miller's cycle separator
  • An application: linear time shortest paths for planar graphs
  • Application: PTAS for finding maximum independent sets in planar graphs

• 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

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

Schedule

Reading Dumplist

• On computing graph minor obstruction sets
• Local treewidth and approximations
• Lovasz review of graph minor theory