Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Tutorial
Tutorial – Topics
The following is just a small selection of possible topics
(papers) for the tutorial.
Please ask for papers on topics you are interested in (you
mind find out which topics these are during the curse of
this lecture).
If you know you are more interested in applications do not
hesitate to ask as well!
Tutorial
Tutorial – Topics
Jianer Chen, Iyad A. Kanj, Ge Xia: Improved upper
bounds for vertex cover. Theor. Comput. Sci.
411(40-42): 3736-3756 (2010);
Yixin Cao, Jianer Chen, Yang Liu: On Feedback Vertex
Set New Measure and New Structures. SWAT 2010:
93-104;
Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, Igor
Razgon: A fixed-parameter algorithm for the directed
feedback vertex set problem. J. ACM 55(5): (2008);
Daniel Marx, Igor Razgon: Fixed-parameter tractability
of multicut parameterized by the size of the cutset.
STOC 2011: 469-478;
Tutorial
Tutorial – Topics
Jiong Guo, Jens Gramm, Falk HÃ1
4 ffner, Rolf Niedermeier,
Sebastian Wernicke: Compression-based
fixed-parameter algorithms for feedback vertex set and
edge bipartization. J. Comput. Syst. Sci. 72(8):
1386-1396 (2006);
Stefan Kratsch, Magnus WahlstrÃPm: Compression via
Matroids: A Randomized Polynomial Kernel for Odd
Cycle Transversal. SODA 2012: 94-103;
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel Bounds for Path and Cycle Problems. IPEC
2011: 145-158;
Hans L. Bodlaender, Bart M. P. Jansen, Stefan
Kratsch:Cross-Composition: A New Technique for
Kernelization Lower Bounds. STACS 2011: 165-176;
Tutorial
Tutorial – Topics
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh,
Dimitrios M. Thilikos: Bidimensionality and Kernels.
SODA 2010: 503-510;
Torben Hagerup: Simpler Linear-Time Kernelization for
Planar Dominating Set. IPEC 2011: 181-193.