LITA - Laboratoire d'Informatique Théorique et Appliquée - Université de Lorraine
Université de Lorraine - Laboratoire d'Informatique Théorique et Appliquée (LITA)
Université de Lorraine - Site de Metz - Île du Saulcy
57045 METZ CEDEX 1
Tel. : 03 87 31 54 45 - Fax : 03 87 31 53 09

Laboratoire d'Informatique Théorique et Appliquée (LITA)

Kratsch Dieter
UFR MIM - Département Informatique

Professeur des universités, membre Permanent du LITA.
Habilité à diriger les recherches
Membre du conseil de laboratoire

equipe Calculs, Graphes et Logique - Responsable d'équipe

UFR MIM - E223
Téléphone0387315444
e-maildieter.kratsch@univ-lorraine.fr
Webhttp://www.lita.univ-lorraine.fr/~kratsch

Publications

Articles dans des revues internationales ou nationales avec comité de lecture répertoriées par l'HCRES

2017 Enumeration and maximum number of minimal connected vertex covers []
P.A. Golovach, P. Heggernes, D. Kratsch
European Journal on Combinatorics (à paraitre)
2017 Output-polynomial enumeration on graphs of bounded (local) linear MIM-width []
M.M. Kante, P.A. Golovach, P. Heggernes, D. Krastch, S.H. Saether, Y. Villanger
Algorithmica, à paraître
2017 Minimal dominating sets in interval graphs and trees [ACL619]
P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, Y. Villanger
Discrete Applied Mathematics (special issue dedicated to the 65th birthday of Andreas Brandstädt), 216 (2017) pages 162-170
2016 Squares of low clique number []
P.A. Golovach, D. Kratsch, D. Paulusma, A. Stewart
Electronic Notes in Discrete Mathematics, 55 (2016) pages 195-198
2016 Parameterized algorithms for finding square roots [ACL75]
M. Cochefert, J.-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma
Algorithmica, 74(2) (2016): 602-629
2016 Finding shortest paths between graph colourings [ACL76]
M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma
Algorithmica : 71(1) (2016): pp.295-312
2016 Enumerating minimal connected dominating sets in graphs of bounded chordality [ACL618]
P.A. Golovach, P. Heggernes, D. Kratsch
Theoretical Computer Science 630 (2016), pp. 63-75
2015 List Coloring in the Absence of a Linear Forest [ACL72]
J.-F. Couturier, P.A. Golovach, D. Kratsch, D. Paulusma
Algorithmica, 71 (1) (2015) pp. 21-35
2015 An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets [ACL73]
P.A. Golovach, P. Heggernes, D. Kratsch, Y. Villanger
Algorithmica, 72 (3) (2015) pp. 836-859
2015 Exact Algorithms for Kayles [ACL74]
H.L. Bodlaender, D. Kratsch, S.T. Timmer
Theoretical Computer Science 562 (2015) pp. 165-176
2015 Enumerating minimal dominating sets in chordal bipartite graphs [ACL71]
P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, Y. Villanger
Discrete Applied Mathematics, special issue GROW 2013,199 (2016), pp. 30-36
2015 Algorithms solving the Matching Cut problem [ACL77]
D. Kratsch, V. Bang Le
Theoretical Computer Science, 609 (2016), pp. 328-335
2014 Enumerating minimal subset feedback vertex sets [ACL86]
F.V. Fomin, P. Heggernes, D. Kratsch, C. Papadopoulos, Y. Villanger
Algorithmica 69, pp 216-231 (2014)
2014 An exact algorithm for Subset Feedback Vertex Set on chordal graphs [ACL87]
P.A. Golovach, P. Heggernes, D. Kratsch, R. Saei
Journal of Discrete Algorithms 26, pp7-15, 2014
2014 Finding clubs in graph classes [ACL88]
P. Golovach, P. Heggernes, D. Kratsch, A. Rafiey
Discrete Applied Mathematics 174 (2014), pp 113-129
2014 Identification of sub-grains and low angle boundaries beyond the angular resolution of EBSD maps [ACL89]
L. Germain, D. Kratsch, M. Salib, N. Gey
Materials Characterization, volume 98, December 2014, pp 66-72
2013 Computing optimal Steiner trees in polynomial space [ACL90]
F. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov, S. Saurabh
Algorithmica, 65 (2013) pp. 584–604
2013 Fully decomposable split graphs [ACL91]
H. Broersma, D. Kratsch, G. Woeginger
European Journal on Combinatorics, 34 (2013) pp. 567–575
2013 Minimal dominating sets in graph classes: combinatorial bounds and enumeration [ACL92]
J.-F. Couturier, P. Heggernes, P. van't Hof, D. Kratsch
Theoretical Computer Science (2013), 487 (2013), pp. 82–94
2013 Colorings with few colors: counting, enumeration and combinatorial bounds [ACL93]
J.-F. Couturier, P.A. Golovach, D. Kratsch, M. Liedloff, A. Pyatkin
Theory of Computing Systems, 52 (2013), pp. 645–667
2013 Detecting induced minors in AT-free graphs [ACL94]
P. Golovach, D. Kratsch, D. Paulusma
Theoretical Computer Science, 482 (2013), pp. 20–32
2013 Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing [ACL95]
P. Heggernes, D. Kratsch, D. Lokshtanov, V. Raman, S. Saurabh
Information & Computation 231 (2013) pp 109-116
2012 A note on exact algorithms for vertex ordering problems on graphs [ACL98]
H.L. Bodlaender, F.V. Fomin, M.C.A. Koster, D. Kratsch, D.M. Thilikos
Theory of Computing Systems 50 (2012) pp. 420–432
2012 Exact algorithms for treewidth [ACL99]
H.L. Bodlaender, F.V. Fomin, M.C.A. Koster, D. Kratsch, D.M. Thilikos
ACM Transcactions on Algorithms, 9(1): (2012), article 12; 23 pages
2012 Bicolored independent set and bicliques [ACL100]
J.-F. Couturier, D. Kratsch
Information Processing Letters 112 (2012) pp. 329–334
2012 On the parameterized complexity of coloring graphs in the absence of a linear forest [ACL101]
J.-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma
Journal on Discrete Algorithms 15 (2012) pp. 56–62
2012 On independent sets and bicliques [ACL102]
S. Gaspers, D. Kratsch, M. Liedloff
Algorithmica 62 (2012) pp. 637–658
2011 Breaking the 2n-barrier for irredundance: two lines of attack [ACL107]
D. Binkele-Raible, L. Brankovic, M. Cygan, H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, M. Pilipczuk, P. Rossmanith, J.O. Wojtaszczyk
Journal of Discrete Algorithms 9 (2011) pp. 214–230
2011 Exact algorithms for L(2; 1)-labeling of graphs [ACL108]
F. Havet, M. Klazar, J. Kratochvil, D. Kratsch, M. Liedloff
Algorithmica 59 (2011) pp. 169–194
2011 Branch and Recharge : Exact algorithms for generalized domination [ACL109]
F.V. Fomin, P.A. Golovach, J. Kratochvil, D. Kratsch, M. Liedloff
Algorithmica 61 (2011) pp. 252–273
2011 A fast exact algorithm for the Maximum Leaf Spanning Tree problem [ACL110]
H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible, P. Rossmanith
Theoretical Computer Science 412 (2011) pp. 6290 – 6302
2011 Bandwidth on AT-free graphs [ACL111]
P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov, D.Meister, S. Saurabh
Theoretical Computer Science 412 (2011) pp. 7001 – 7008

Articles dans les proceedings de conférences internationales avec comité de lecture

2017 Enumerating minimal tropical connected sets []
D. Kratsch, M. Liedloff, M. Y. Sayadi
Proceedings of SOFSEM 2017, Springer, 2017, LNCS 10139, pages 217-228
2017 Enumeration and Maximum Number of Maximal Irredundant Sets for Claw-Free Graphs []
P. Golovach, D. Kratsch, M. Liedloff
Proceedings of CIAC 2017, à paraitre
2016 Enumeration and maximum number of minimal connected vertex covers [ACTI64]
P.A. Golovach, P. Heggernes, D. Kratsch
Proceedings of IWOCA 2015, à paraitre
2016 Faster algorithms to enumerate hypergraph transversals [ACTI66]
M. Cochefert, J.-F. Couturier, S. Gaspers, D. Kratsch
Proceedings of LATIN 2016, LNCS 9644, pp. 306-318
2016 A Linear Kernel for Finding Square Roots of Almost Planar Graphs [ACTI620]
P. Golovach, D. Kratsch, D. Paulusma, A. Stewart
Proceedings of SWAT 2016, LIPIcs 53, Schloss Dagstuhl, Leibniz – Zentrum für Informatik, 2016, pp. 4:1 – 4:14
2016 Finding Cactus Roots in Polynomial Time [ACTI622]
P. Golovach, D. Kratsch, D. Paulusma, A. Stewart
Proceedings of IWOCA 2016, Springer, 2016, LNCS 9843, pages 361-372
2016 Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs [ACTI623]
F. Kammer, D. Kratsch, M. Laudahn
Proceedings of MFCS 2016, Springer, 2016, LNCS 9843, pages 56:1-56:14
2015 Algorithms solving the Matching Cut problem [ACTI61]
D. Kratsch, V. Bang Le
Proceedings of CIAC 2015, Springer, 2015, LNCS 9079, pp. 288 – 299
2015 End-vertices of graph search algorithms, [ACTI62]
D. Kratsch, M. Liedloff, D. Meister
Proceedings of CIAC 2015, Springer, 2015, LNCS 9097, pp. 300 - 311
2015 Enumerating minimal connected dominating sets in graphs of bounded chordality [ACTI63]
P.A. Golovach, P. Heggernes, D. Kratsch
Proceedings of IPEC 2015, LIPIcs, Dagstuhl, 2015, pp. 307 - 318.
2015 Output-polynomial enumeration on graphs of bounded (local) linear MIM-width [ACTI65]
M.M. Kanté, P.A. Golovach, P. Heggernes, D. Kratsch, S.H. Saether, Y. Villanger
Proceedings of ISAAC 2015, Springer-Verlag, 2015, LNCS 9472, pp. 248-258
2015 Enumeration and maximum number of minimal connected vertex covers in Graphs [ACTI614]
P.A. Golovach, P. Heggernes, D. Kratsch
Springer, 2015, Proceedings of IWOCA 2015, pp. 237-247
2014 Exact algorithms to clique-colour graphs [ACTI71]
M. Cochefert, D. Kratsch
Proceedings of SOFSEM 2014 Springer-Verlag, 2014 Berlin, LNCS 8327, pp. 187 – 198
2014 Finding shortest paths between graph colourings [ACTI72]
M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma
Proceedings of IPEC 2014, Springer, 2014, LNCS 8894, pp. 221 - 233
2014 Exact exponential algorithms to find tropical connected sets of minimum size [ACTI73]
M. Chapelle, M. Cochefert, D. Kratsch, R. Letourneur, M. Liedloff
Proceedings of IPEC 2014, Springer, 2014, Berlin, LNCS 8894, pp. 147 – 158
2013 The jump number problem : exact and parameterized [ACTI77]
D. Kratsch, S. Kratsch
Proceedings of IPEC 2013 Springer-Verlag, 2013 Berlin, LNCS 8246, pp. 230 – 242
2013 Exact Algorithms for Weak Roman Domination [ACTI78]
M. Chapelle, M. Cochefert, J.-F. Couturier, D. Kratsch, A. Perez, M. Liedloff
Proceedings of IWOCA 2013 Springer-Verlag, 2013 Berlin, LNCS 8288, pp. 81 – 93
2013 Sparse square roots [ACTI79]
M. Cochefert, J.-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma
Proceedings of WG 2013 Springer-Verlag, 2013 Berlin, LNCS 8165, pp. 177–188
2013 Cliques and clubs [ACTI80]
P. Golovach, P. Heggernes, D. Kratsch, A. Rafiey
Proceedings of CIAC 2013 Springer-Verlag, 2013 Berlin, LNCS 7878, pp. 276–287
2013 An incremental polynomial time algorithm to enumerate all minimal edge dominating sets [ACTI81]
P. Golovach, P. Heggernes, D. Kratsch, Y. Villanger
Proceedings of ICALP 2013 Part I, Springer-Verlag, 2013 Berlin, LNCS 7965, pp. 485–496
2012 Colouring AT-free graphs [ACTI85]
D. Kratsch, H. Müller
Proceedings of ESA 2012 Springer-Verlag, 2012 Berlin, LNCS 7501, pp. 707–718
2012 Minimal dominating sets in graph classes: combinatorial bounds and enumeration [ACTI86]
J.-F. Couturier, P. Heggernes, P. van’t Hof, D. Kratsch
Proceedings of SOFSEM 2012Springer-Verlag, 2012 Berlin, LNCS 7147, pp. 202–213
2012 Detecting induced minors in AT-free graphs [ACTI87]
P. Golovach, D. Kratsch, D. Paulusma
Proceedings of ISAAC 2012 Springer-Verlag, 2012 Berlin, LNCS 7676, pp. 495–505
2012 An exact algorithm for Subset Feedback Vertex Set on chordal graphs [ACTI88]
P.A. Golovach, P. Heggernes, D. Kratsch, R. Saei
Proceedings of IPEC 2012 Springer-Verlag, 2012 Berlin, LNCS 7535, pp. 85–96
2011 Enumerating minimal subset feedback vertex sets [ACTI93]
F. Fomin, P. Heggernes, D. Kratsch, C. Papadopoulos, Y. Villanger
Proceedings of WADS 2011Springer-Verlag, 2011Berlin, LNCS 6844, pp. 399–410
2011 Exact algorithms for Kayles [ACTI94]
H.L. Bodlaender, D. Kratsch
Proceedings of WG 2011Springer- Verlag, 2011Berlin, LNCS 6986, pp. 59–70
2011 Bicolored independent set and bicliques [ACTI95]
J.-F. Couturier, D. Kratsch
Proceedings of CTW 2011pp. 130–133
2011 List coloring in the absence of a linear forest [ACTI96]
J.-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma
Proceedings of WG 2011Springer-Verlag, 2011Berlin, LNCS 6986, pp. 119–130

Conférences données à l'invitation du Comité d'organisation dans un congrès national ou international.

2015 Enumeration Algorithms and Structure [INV624]
D. Kratsch
Leiden, The Netherlands, 2015, Tutorial on input-sensitive enumeration, aout 24-28 (90min)
2014 Exact exponential time algorithms for variants of the graph homomorphism problem [INV8]
D. Kratsch
7th Workshop on Algebraic, Topological and Complexity Aspects of Graph Cover (ATCAGC), Calheta, Madeira, Portugal, keynote speaker (60 min.), 24.1.-30.1.;
2012 Exact exponential algorithms [INV9]
Dieter Kratsch
4th Polish Combinatorial Conference, Bedlewo, Pologne, 2012

Communications orales sans actes dans un congrès international ou national.

2016 On maximal Irredundant Sets and (sigma, rho)-Dominating Sets in Path []
P. Golovach, D. Kratsch, M. Liedloff, M. Rao, M. Y. Sayadi
WEPA 2016, Clermont-Ferrand
2015 Tutorial Input-Sensitive Enumeration [COM48]
Dieter Kratsch
Leiden, Pays Bas, 2015
2015 Enumeration of minimal connected dominating sets and minimal connected vertex covers [COM49]
Dieter Kratsch
GROW 2015, Aussois, France, 2015
2013 The jump number problem : Exact and parameterized [COM38]
Dieter Kratsch
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time, Dagstuhl, Allemagne, 2013 Dagstuhl-Seminar 13331
2013 Journée de l’equipe GAMoC [COM39]
Dieter Kratsch
«Cliques and Clubs» Orleans, 2013 Université d'Orléans
2012 Minimal dominating sets in graphs: enumeration , combinatorial bounds and graph classes » [COM41]
Dieter Kratsch
Clermont-Ferrand, 2012 JCRAA (Journées Combinatoires Rhone-Alpes Auvergne)
2012 AT-free graphs : Structure and algorithms [COM42]
Dieter Kratsch
colloque de l’honneur pour le 50e anniversaire de Jan-Arne Telle, Bergen, Norvège, 2012
2012 Lower bounds in parameterized complexity [COM43]
Dieter Kratsch
Premières Journées du GT Complexité et Algorithmes, Paris, 2012
2011 Les ensembles stables d’un graphe : approche algorithmique [COM44]
Dieter Kratsch
Nancy, 2011 Colloque Graphes : Enseignement et Applications Industrielles

Directions d'ouvrages ou de revues.

2017 Preface: Special graph classes and algorithms []
F. Dragan, D. Kratsch, V.B. Le
in honor of Professor Andreas Brandstädt on the occasion of his 65th birthday. Discrete Applied Mathematics 216: 1 (2017)
2016 Selected Papers from WG 2014 [DO625]
D. Kratsch, I. Todinca
Guest Editorial ; Algorithmica, 2016, 75(1): p. 186.
2014 Proceedings of WG 2014 [DO12]
D. Kratsch, I. Todinca
Springer, 2014, LNCS 8747, 436 pp.

Ouvrages scientifiques (ou chapitres de ces ouvrages).

2015 Exact algorithms for dominating set [OS3]
D. Kratsch
In: Encyclopedia of Algorithms. Ming-Yang Kao, ed., Springer, 2016, pp. 667-670