Stefan Kratsch

Cited by

	All	Since 2020
Citations	3384	1528
h-index	30	21
i10-index	61	44

340

170

255

201020112012201320142015201620172018201920202021202220232024202520 37 104 215 223 215 210 231 260 275 320 242 252 321 304 83

Public access

View all

40 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
Michał PilipczukUniversity of WarsawVerified email at mimuw.edu.pl
Dániel MarxCISPA Helmholtz Center for Information SecurityVerified email at cispa.saarland
Marek CyganUniversity of WarsawVerified email at mimuw.edu.pl
Jesper NederlofUtrecht UniversityVerified email at uu.nl
Yngve VillangerUniversity of BergenVerified email at uib.no
Robert BredereckTU ClausthalVerified email at tu-clausthal.de
Fedor V. FominProfessor of Computer Science, University of BergenVerified email at uib.no
Manuel SorgeTU WienVerified email at ac.tuwien.ac.at
Stefan FafianieUniversity of BonnVerified email at cs.uni-bonn.de
Jiehua ChenTU ViennaVerified email at tuwien.ac.at
Danny HermelinBen-Gurion University of the NegevVerified email at bgu.ac.il
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
Dieter Kratschprofesseur d'informatique, Universite de LorraineVerified email at univ-lorraine.fr
Frank NeumannOptimisation and Logistics, School of ComputerVerified email at adelaide.edu.au
Xi WuGoogleVerified email at google.com

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	370*	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	310	2015
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	153	2013
Fast hamiltonicity checking via bases of perfect matchings M Cygan, S Kratsch, J Nederlof Journal of the ACM (JACM) 65 (3), 1-46, 2018	141	2018
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	137	2014
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	132	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	110*	2014
Recent developments in kernelization: A survey S Kratsch Bulletin of EATCS 2 (113), 2014	102	2014
Two edge modification problems without polynomial kernels S Kratsch, M Wahlström Discrete Optimization 10 (3), 193-199, 2013	102	2013
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	92*	2015
Fixed-parameter evolutionary algorithms and the vertex cover problem S Kratsch, F Neumann Proceedings of the 11th Annual conference on Genetic and evolutionary …, 2009	89	2009
Preprocessing for treewidth: A combinatorial analysis through kernelization HL Bodlaender, BMP Jansen, S Kratsch SIAM Journal on Discrete Mathematics 27 (4), 2108-2142, 2013	83	2013
Data reduction for graph coloring problems BMP Jansen, S Kratsch Information and Computation 231, 70-88, 2013	73	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	71	2020
Finding shortest paths between graph colourings M Johnson, D Kratsch, S Kratsch, V Patel, D Paulusma Algorithmica 75 (2), 295-321, 2016	63	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	59	2013
Polynomial kernels for weighted problems M Etscheid, S Kratsch, M Mnich, H Röglin Journal of Computer and System Sciences 84, 1-10, 2017	58	2017
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	58	2016
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
Kernel bounds for path and cycle problems HL Bodlaender, BMP Jansen, S Kratsch Theoretical Computer Science 511, 117-136, 2013	58	2013

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