Stefan Kratsch

Cited by

	All	Since 2018
Citations	3005	1703
h-index	30	23
i10-index	56	44

340

170

255

2009201020112012201320142015201620172018201920202021202220238 18 36 101 211 216 215 208 233 247 259 328 256 282 320

Public access

View all

37 articles

3 articles

available

not available

Based on funding mandates

Co-authors

Magnus WahlströmRoyal Holloway, University of LondonVerified email at rhul.ac.uk
Hans L. BodlaenderProfessor Computer Science, Utrecht UniversityVerified email at uu.nl
Bart M. P. JansenAssociate Professor, Eindhoven University of TechnologyVerified email at tue.nl
Marcin PilipczukInstytut Informatyki, Uniwersytet WarszawskiVerified email at mimuw.edu.pl
Marek CyganUniversity of WarsawVerified email at mimuw.edu.pl
Michał PilipczukUniversity of WarsawVerified email at mimuw.edu.pl
Dániel MarxCISPA Helmholtz Center for Information SecurityVerified email at cispa.saarland
Jesper NederlofUtrecht UniversityVerified email at uu.nl
Yngve VillangerUniversity of BergenVerified email at uib.no
Manuel SorgeTU WienVerified email at ac.tuwien.ac.at
Robert BredereckTU ClausthalVerified email at tu-clausthal.de
Fedor V. FominProfessor of Computer Science, University of BergenVerified email at uib.no
Stefan FafianieUniversity of BonnVerified email at cs.uni-bonn.de
Jiehua ChenTU ViennaVerified email at tuwien.ac.at
Gerhard WoegingerProfessor of Computer Science, RWTH AachenVerified email at cs.rwth-aachen.de
Klaus JansenProfessor, Computer Science, University of KielVerified email at informatik.uni-kiel.de
Frank NeumannOptimisation and Logistics, School of ComputerVerified email at adelaide.edu.au
Dieter Kratschprofesseur d'informatique, Universite de LorraineVerified email at univ-lorraine.fr
Xi WuGoogleVerified email at google.com
Daniel PaulusmaDepartment of Computer Science, Durham UniversityVerified email at durham.ac.uk

Stefan Kratsch

Professor at Humboldt University Berlin

Verified email at informatik.hu-berlin.de - Homepage

Theoretical Computer Science Parameterized Complexity Kernelization


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
Kernelization lower bounds by cross-composition HL Bodlaender, BMP Jansen, S Kratsch SIAM Journal on Discrete Mathematics 28 (1), 277-305, 2014	346*	2014
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth HL Bodlaender, M Cygan, S Kratsch, J Nederlof Information and Computation 243, 86-111, 2015	273	2015
Compression via matroids: a randomized polynomial kernel for odd cycle transversal S Kratsch, M Wahlström ACM Transactions on Algorithms (TALG) 10 (4), 1-15, 2014	124	2014
Fast hamiltonicity checking via bases of perfect matchings M Cygan, S Kratsch, J Nederlof Journal of the ACM (JACM) 65 (3), 1-46, 2018	122	2018
Bin packing with fixed number of bins revisited K Jansen, S Kratsch, D Marx, I Schlotter Journal of Computer and System Sciences 79 (1), 39-49, 2013	119	2013
Representative sets and irrelevant vertices: New tools for kernelization S Kratsch, M Wahlström 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 450-459, 2012	119	2012
Tight bounds for parameterized complexity of cluster editing with a small number of clusters FV Fomin, S Kratsch, M Pilipczuk, M Pilipczuk, Y Villanger Journal of Computer and System Sciences 80 (7), 1430-1447, 2014	101*	2014
Recent developments in kernelization: A survey S Kratsch Bulletin of EATCS 2 (113), 2014	98	2014
Two edge modification problems without polynomial kernels S Kratsch, M Wahlström Discrete Optimization 10 (3), 193-199, 2013	96*	2013
Fixed-parameter evolutionary algorithms and the vertex cover problem S Kratsch, F Neumann Proceedings of the 11th Annual conference on Genetic and evolutionary …, 2009	86	2009
A completeness theory for polynomial (Turing) kernelization D Hermelin, S Kratsch, K Sołtys, M Wahlström, X Wu Algorithmica 71 (3), 702-730, 2015	85*	2015
Preprocessing for treewidth: A combinatorial analysis through kernelization HL Bodlaender, BMP Jansen, S Kratsch SIAM Journal on Discrete Mathematics 27 (4), 2108-2142, 2013	79	2013
Data reduction for graph coloring problems BMP Jansen, S Kratsch Information and Computation 231, 70-88, 2013	64	2013
Clique cover and graph separation: New incompressibility results M Cygan, S Kratsch, M Pilipczuk, M Pilipczuk, M Wahlström ACM Transactions on Computation Theory (TOCT) 6 (2), 1-19, 2014	58	2014
Finding shortest paths between graph colourings M Johnson, D Kratsch, S Kratsch, V Patel, D Paulusma Algorithmica 75 (2), 295-321, 2016	56*	2016
Parameterized complexity of vertex deletion into perfect graph classes P Heggernes, P Van’t Hof, BMP Jansen, S Kratsch, Y Villanger Theoretical Computer Science 511, 172-180, 2013	55	2013
Kernel bounds for path and cycle problems HL Bodlaender, BMP Jansen, S Kratsch Theoretical Computer Science 511, 117-136, 2013	53	2013
Representative sets and irrelevant vertices: New tools for kernelization S Kratsch, M Wahlström Journal of the ACM (JACM) 67 (3), 1-50, 2020	50	2020
Point line cover: The easy kernel is essentially tight S Kratsch, G Philip, S Ray ACM Transactions On Algorithms (TALG) 12 (3), 1-16, 2016	47	2016
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem S Kratsch ACM Transactions on Algorithms (TALG) 10 (4), 1-16, 2014	44	2014

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow

Cited by

Co-authors