Stefan Kratsch
Stefan Kratsch
Professor at Humboldt University Berlin
Geverifieerd e-mailadres voor informatik.hu-berlin.de - Homepage
Titel
Geciteerd door
Geciteerd door
Jaar
Kernelization lower bounds by cross-composition
HL Bodlaender, BMP Jansen, S Kratsch
SIAM Journal on Discrete Mathematics 28 (1), 277-305, 2014
259*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
1822015
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
1132012
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
942014
Two edge modification problems without polynomial kernels
S Kratsch, M Wahlström
Discrete Optimization 10 (3), 193-199, 2013
82*2013
Recent developments in kernelization: A survey
S Kratsch
Bulletin of EATCS 2 (113), 2014
812014
Fast Hamiltonicity checking via bases of perfect matchings
M Cygan, S Kratsch, J Nederlof
Journal of the ACM (JACM) 65 (3), 1-46, 2018
76*2018
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
72*2014
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
722013
Preprocessing for treewidth: A combinatorial analysis through kernelization
HL Bodlaender, BMP Jansen, S Kratsch
SIAM Journal on Discrete Mathematics 27 (4), 2108-2142, 2013
632013
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
62*2015
Fixed-parameter evolutionary algorithms and the vertex cover problem
S Kratsch, F Neumann
Algorithmica 65 (4), 754-771, 2013
612013
Finding shortest paths between graph colourings
M Johnson, D Kratsch, S Kratsch, V Patel, D Paulusma
Algorithmica 75 (2), 295-321, 2016
47*2016
Data reduction for graph coloring problems
BMP Jansen, S Kratsch
Information and Computation 231, 70-88, 2013
472013
Fixed-parameter tractability of multicut in directed acyclic graphs
S Kratsch, M Pilipczuk, M Pilipczuk, M Wahlström
SIAM Journal on Discrete Mathematics 29 (1), 122-144, 2015
452015
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
452014
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
402014
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
382016
Kernel bounds for path and cycle problems
HL Bodlaender, BMP Jansen, S Kratsch
Theoretical Computer Science 511, 117-136, 2013
382013
A multivariate complexity analysis of lobbying in multiple referenda
R Bredereck, J Chen, S Hartung, S Kratsch, R Niedermeier, O Suchy, ...
Journal of Artificial Intelligence Research 50, 409-446, 2014
352014
Het systeem kan de bewerking nu niet uitvoeren. Probeer het later opnieuw.
Artikelen 1–20