Dieter Kratsch

Publication Activity (10 Years)

Years Active: 1985-2022
Publications (10 Years): 40

Top Venues

CoRR

Algorithmica

Theor. Comput. Sci.

Discret. Appl. Math.

Publications

Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, Van Bang Le
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. J. Comput. Syst. Sci. 123 (2022)
Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, Van Bang Le
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. CoRR (2021)
Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, Van Bang Le
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. STACS (2021)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
Enumeration of minimal connected dominating sets for chordal graphs. Discret. Appl. Math. 278 (2020)
Christian Komusiewicz, Dieter Kratsch, Van Bang Le
Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms. Discret. Appl. Math. 283 (2020)
Petr A. Golovach, Dieter Kratsch, Mohamed Yosri Sayadi
Enumeration of maximal irredundant sets for claw-free graphs. Theor. Comput. Sci. 754 (2019)
Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi
Enumeration and maximum number of minimal dominating sets for chordal graphs. Theor. Comput. Sci. 783 (2019)
Frank Kammer, Dieter Kratsch, Moritz Laudahn
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. Algorithmica 81 (3) (2019)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, Daniël Paulusma
Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. Algorithmica 81 (7) (2019)
Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi
Enumeration and maximum number of maximal irredundant sets for chordal graphs. Discret. Appl. Math. 265 (2019)
Mathieu Chapelle, Manfred Cochefert, Jean-François Couturier, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff, Anthony Perez
Exact algorithms for weak Roman domination. Discret. Appl. Math. 248 (2018)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
Finding Cactus Roots in Polynomial Time. Theory Comput. Syst. 62 (6) (2018)
Christian Komusiewicz, Dieter Kratsch, Van Bang Le
Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. IPEC (2018)
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
Computing square roots of graphs with low maximum degree. Discret. Appl. Math. 248 (2018)
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, Yngve Villanger
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica 80 (2) (2018)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Enumeration and maximum number of minimal connected vertex covers in graphs. Eur. J. Comb. 68 (2018)
Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi
Enumerating Minimal Tropical Connected Sets. SOFSEM (2017)
Feodor F. Dragan, Dieter Kratsch, Van Bang Le
Preface: Special graph classes and algorithms-in honor of Professor Andreas Brandstädt on the occasion of his 65th birthday. Discret. Appl. Math. 216 (2017)
Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff
Exact exponential algorithms to find tropical connected sets of minimum size. Theor. Comput. Sci. 676 (2017)
Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi
Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs. WG (2017)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, Daniël Paulusma
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. CoRR (2017)
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Yngve Villanger
Minimal dominating sets in interval graphs and trees. Discret. Appl. Math. 216 (2017)
Petr A. Golovach, Dieter Kratsch, Mohamed Yosri Sayadi
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs. CIAC (2017)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, Daniël Paulusma
Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. WG (2017)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
A linear kernel for finding square roots of almost planar graphs. Theor. Comput. Sci. 689 (2017)
Frank Kammer, Dieter Kratsch, Moritz Laudahn
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. MFCS (2016)
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Parameterized Algorithms for Finding Square Roots. Algorithmica 74 (2) (2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
A Linear Kernel for Finding Square Roots of Almost Planar Graphs. SWAT (2016)
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
Squares of Low Maximum Degree. CoRR (2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
Finding Cactus Roots in Polynomial Time. IWOCA (2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
Squares of Low Clique Number. Electron. Notes Discret. Math. 55 (2016)
Manfred Cochefert, Jean-François Couturier, Serge Gaspers, Dieter Kratsch
Faster Algorithms to Enumerate Hypergraph Transversals. LATIN (2016)
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Yngve Villanger
Enumerating minimal dominating sets in chordal bipartite graphs. Discret. Appl. Math. 199 (2016)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. CoRR (2016)
Dieter Kratsch, Ioan Todinca
Guest Editorial: Selected Papers from WG 2014. Algorithmica 75 (1) (2016)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Finding Shortest Paths Between Graph Colourings. Algorithmica 75 (2) (2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart
A Linear Kernel for Finding Square Roots of Almost Planar Graphs. CoRR (2016)
Frank Kammer, Dieter Kratsch, Moritz Laudahn
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. CoRR (2016)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Enumerating minimal connected dominating sets in graphs of bounded chordality. Theor. Comput. Sci. 630 (2016)
Dieter Kratsch, Van Bang Le
Algorithms solving the Matching Cut problem. Theor. Comput. Sci. 609 (2016)
Dieter Kratsch, Mathieu Liedloff, Daniel Meister
End-Vertices of Graph Search Algorithms. CIAC (2015)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. IWOCA (2015)
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, Yngve Villanger
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. CoRR (2015)
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
List Coloring in the Absence of a Linear Forest. Algorithmica 71 (1) (2015)
Hans L. Bodlaender, Dieter Kratsch, Sjoerd T. Timmer
Exact algorithms for Kayles. Theor. Comput. Sci. 562 (2015)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Yngve Villanger
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Algorithmica 72 (3) (2015)
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, Yngve Villanger
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. ISAAC (2015)
Dieter Kratsch, Van Bang Le
Algorithms Solving the Matching Cut Problem. CIAC (2015)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality. IPEC (2015)
Manfred Cochefert, Jean-François Couturier, Serge Gaspers, Dieter Kratsch
Faster algorithms to enumerate hypergraph transversals. CoRR (2015)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Colouring Reconfiguration Is Fixed-Parameter Tractable. CoRR (2014)
Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff
Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size. IPEC (2014)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
Subset feedback vertex sets in chordal graphs. J. Discrete Algorithms 26 (2014)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Finding Shortest Paths Between Graph Colourings. IPEC (2014)
Manfred Cochefert, Dieter Kratsch
Exact Algorithms to Clique-Colour Graphs. SOFSEM (2014)
Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger
Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica 69 (1) (2014)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey
Finding clubs in graph classes. Discret. Appl. Math. 174 (2014)
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Sparse Square Roots. WG (2013)
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, Daniel Lokshtanov, Saket Saurabh
Computing Optimal Steiner Trees in Polynomial Space. Algorithmica 65 (3) (2013)
Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh
Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Inf. Comput. 231 (2013)
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Parameterized Algorithms for Finding Square Roots. CoRR (2013)
Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, Dieter Kratsch
Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theor. Comput. Sci. 487 (2013)
Dieter Kratsch, Stefan Kratsch
The Jump Number Problem: Exact and Parameterized. IPEC (2013)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey
Cliques and Clubs. CIAC (2013)
Hajo Broersma, Dieter Kratsch, Gerhard J. Woeginger
Fully decomposable split graphs. Eur. J. Comb. 34 (3) (2013)
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Artem V. Pyatkin
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds. Theory Comput. Syst. 52 (4) (2013)
Mathieu Chapelle, Manfred Cochefert, Jean-François Couturier, Dieter Kratsch, Mathieu Liedloff, Anthony Perez
Exact Algorithms for Weak Roman Domination. IWOCA (2013)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Detecting induced minors in AT-free graphs. Theor. Comput. Sci. 482 (2013)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Yngve Villanger
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. ICALP (1) (2013)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Detecting Induced Minors in AT-Free Graphs. ISAAC (2012)
Dieter Kratsch, Haiko Müller
Colouring AT-Free Graphs. ESA (2012)
Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos
On exact algorithms for treewidth. ACM Trans. Algorithms 9 (1) (2012)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Yngve Villanger
Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay CoRR (2012)
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
On the parameterized complexity of coloring graphs in the absence of a linear forest. J. Discrete Algorithms 15 (2012)
Serge Gaspers, Dieter Kratsch, Mathieu Liedloff
On Independent Sets and Bicliques in Graphs. Algorithmica 62 (3-4) (2012)
Jean-François Couturier, Dieter Kratsch
Bicolored independent sets and bicliques. Inf. Process. Lett. 112 (8-9) (2012)
Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, Dieter Kratsch
Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration. SOFSEM (2012)
Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos
A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. Theory Comput. Syst. 50 (3) (2012)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. IPEC (2012)
Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk
-barrier for Irredundance: Two lines of attack. J. Discrete Algorithms 9 (3) (2011)
Jean-François Couturier, Dieter Kratsch
Bicolored independent sets and bicliques. CTW (2011)
Hans L. Bodlaender, Dieter Kratsch
Exact Algorithms for Kayles. WG (2011)
Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff
Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica 61 (2) (2011)
Frédéric Havet, Martin Klazar, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff
(2, 1)-Labeling of Graphs. Algorithmica 59 (2) (2011)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh
Bandwidth on AT-free graphs. Theor. Comput. Sci. 412 (50) (2011)
Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger
Enumerating Minimal Subset Feedback Vertex Sets. WADS (2011)
Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith
An exact algorithm for the Maximum Leaf Spanning Tree problem. Theor. Comput. Sci. 412 (45) (2011)
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
List Coloring in the Absence of a Linear Forest. WG (2011)
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin
10441 Abstracts Collection - Exact Complexity of NP-hard Problems. Exact Complexity of NP-hard Problems (2010)
Daniel Binkele-Raible, Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Peter Rossmanith
-Barrier for Irredundance. CIAC (2010)
Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh
Iterative compression and exact algorithms. Theor. Comput. Sci. 411 (7-9) (2010)
Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh
Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. SWAT (2010)
Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Dieter Kratsch, Saket Saurabh
Parameterized algorithm for eternal vertex cover. Inf. Process. Lett. 110 (16) (2010)
Petr A. Golovach, Dieter Kratsch, Jean-François Couturier
Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds. WG (2010)
Hajo Broersma, Dieter Kratsch, Gerhard J. Woeginger
Fully Decomposable Split Graphs. IWOCA (2009)
Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca
Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans. Algorithms 6 (1) (2009)
Iyad A. Kanj, Dieter Kratsch
Convex Recoloring Revisited: Complexity and Exact Algorithms. COCOON (2009)
Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith
Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles CoRR (2009)
Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Daniel Raible
Exact Exponential-Time Algorithms for Finding Bicliques in a Graph. CTW (2009)
Pinar Heggernes, Dieter Kratsch, Daniel Meister
Bandwidth of bipartite permutation graphs in polynomial time. J. Discrete Algorithms 7 (4) (2009)

Dieter Kratsch.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Dieter Kratsch