Outline
This course is a seminar course for PhD students in CSE and SS. The aim is to read recent papers from major conferences in theoretical computer science. Each student should present one paper and write a report on the paper.
This term, the reading list is a set of papers from ESA 2009. If you signed up for this course, you should choose a paper you like and send me email (rudolf@fudan.edu.cn); papers will be assigned first-come-first-serve. The remaining papers will be assigned during the first class on Sep 15. You may also suggest other papers from ESA 2009 (see also LNCS 5757) you want to present.
| Kernel bounds for disjoint cycles and disjoint paths. | H.L. Bodlaender, S. Tomasse, and A. Yeo |
| Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard. | C. Dürr, F. Guinez, and M. Matamala (best paper award) |
| Contraction bidimensionality: The accurate picture. | F.V. Fomin, P. Golovach, and D.M. Thilikos |
| Disproof of the Neighborhood Conjecture with implications to SAT. | H. Gebauer (best student paper award) |
| Maximum flow in directed planar graphs with vertex capacities. | H. Kaplan and Y. Nussbaum |
| Hyperbolic dovetailing. | D. Kirkpatrick |
| Constant ratio fixed-parameter approximation of the edge multicut problem. | D. Marx and I. Razgon |
| Dynamic programmming on tree decompositions using generalised fast subset convolution. | J.M.M. van Rooji, H.L. Bodlaender, and P. Rossmanith |