GRADUATE STUDENT SEMINAR, Treewidth and other width parameters, Tara Abrishami

Graduate Student Seminars
  • Tara Abrishami
  • Princeton University
  • Treewidth and other width parameters 
Mar 6, 2023
12:30 pm
Fine Hall 214

Treewidth and other width parameters 

Treewidth is a measure of the complexity of a graph's structure: roughly speaking, graphs with small treewidth are "simple" and graphs with large treewidth are "complicated."  Treewidth has important applications to algorithms: problems that are NP-hard to solve in general can be solved in polynomial time in graphs with small treewidth. In this talk, we survey some recent results related to treewidth and to similar width parameters, describing their properties and applications.