Stefan Kratsch

Best Publications

• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

  Hans L. Bodlaender;Marek Cygan;Stefan Kratsch;Jesper Nederlof

  259
  Citations

• Kernelization lower bounds by cross-composition

  HL Hans Bodlaender;Bmp Bart Jansen;Stefan Kratsch

  241
  Citations

• Cross-Composition: A New Technique for Kernelization Lower Bounds

  HL Hans Bodlaender;Bmp Bart Jansen;Stefan Kratsch

  179
  Citations

• Representative Sets and Irrelevant Vertices: New Tools for Kernelization

  Stefan Kratsch;Magnus WahlströM

  174
  Citations

• Bin packing with fixed number of bins revisited

  Klaus Jansen;Stefan Kratsch;DáNiel Marx;Ildikó Schlotter

  131
  Citations

• Representative Sets and Irrelevant Vertices: New Tools for Kernelization

  Stefan Kratsch;Magnus Wahlstrom

  128
  Citations

• Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

  Stefan Kratsch;Magnus Wahlström

  126
  Citations

• Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

  Stefan Kratsch;Frank Neumann

  113
  Citations

• Fast Hamiltonicity Checking Via Bases of Perfect Matchings

  Marek Cygan;Stefan Kratsch;Jesper Nederlof

  106
  Citations

• Two Edge Modification Problems without Polynomial Kernels

  Stefan Kratsch;Magnus Wahlström

  96
  Citations

• Recent developments in kernelization: A survey

  Stefan Kratsch

  94
  Citations

• A Completeness Theory for Polynomial (Turing) Kernelization

  Danny Hermelin;Stefan Kratsch;Karolina Sołtys;Magnus Wahlström

  85
  Citations

• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

  Unknown

  84
  Citations

• Data reduction for graph coloring problems

  Bart M. P. Jansen;Stefan Kratsch

  83
  Citations

• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

  Hans L. Bodlaender;Bart M. P. Jansen;Stefan Kratsch

  77
  Citations

• Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

  Fedor V. Fomin;Stefan Kratsch;Marcin Pilipczuk;Michał Pilipczuk

  71
  Citations

• Fixed-parameter Tractability of Multicut in Directed Acyclic Graphs

  Stefan Kratsch;Marcin Pilipczuk;MichaŁ Pilipczuk;Magnus Wahlström

  62
  Citations

• Kernel bounds for path and cycle problems

  Hans L. Bodlaender;Bart M. P. Jansen;Stefan Kratsch

  61
  Citations

• Isomorphism for graphs of bounded feedback vertex set number

  Stefan Kratsch;Pascal Schweitzer

  59
  Citations

• Clique Cover and Graph Separation: New Incompressibility Results

  Marek Cygan;Stefan Kratsch;Marcin Pilipczuk;Michał Pilipczuk

  56
  Citations