Combinatorics Seminar

When: Sunday, April 19, 10am Where: Schreiber 309 Speaker: Zvi Gregory Gutin (Royal Holloway, U. London) Title: Parameterized Combinatorial Optimization

Abstract:

We'll survey some results on well-known combinatorial optimization problems under various parameterizations. For example, the mixed chinese postman problem is fixed-parameter tractable when parameterized by the number of undirected edges, directed edges, or tree-depth of the underlying graph. Somewhat surprisingly, the problem is W[1]-hard when parameterized by the treewidth of the underlying graph. Among other problems, we'll consider the directed and undirected rural postman problems, and TSP.