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
| Téléphone | 0387315444 |
|---|---|
| dieter.kratsch@univ-lorraine.fr | |
| Web | http://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 | 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 |
| 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 |
| 2015 | Exact Algorithms for Kayles [ACL74] H.L. Bodlaender, D. Kratsch, S.T. Timmer Theoretical Computer Science 562 (2015) pp. 165-176 |
| 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 | 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 | 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 | 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 |
| 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 | 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 | Fully decomposable split graphs [ACL91] H. Broersma, D. Kratsch, G. Woeginger European Journal on Combinatorics, 34 (2013) pp. 567–575 |
| 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 |
| 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 | 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 independent sets and bicliques [ACL102] S. Gaspers, D. Kratsch, M. Liedloff Algorithmica 62 (2012) pp. 637–658 |
| 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 | 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 | 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 | Enumeration and Maximum Number of Maximal Irredundant Sets for Claw-Free Graphs [] P. Golovach, D. Kratsch, M. Liedloff Proceedings of CIAC 2017, à paraitre |
| 2017 | Enumerating minimal tropical connected sets [] D. Kratsch, M. Liedloff, M. Y. Sayadi Proceedings of SOFSEM 2017, Springer, 2017, LNCS 10139, pages 217-228 |
| 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 | 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 |
| 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 | Enumeration and maximum number of minimal connected vertex covers [ACTI64] P.A. Golovach, P. Heggernes, D. Kratsch Proceedings of IWOCA 2015, à paraitre |
| 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 |
| 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 |
| 2015 | Algorithms solving the Matching Cut problem [ACTI61] D. Kratsch, V. Bang Le Proceedings of CIAC 2015, Springer, 2015, LNCS 9079, pp. 288 – 299 |
| 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 |
| 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 algorithms to clique-colour graphs [ACTI71] M. Cochefert, D. Kratsch Proceedings of SOFSEM 2014 Springer-Verlag, 2014 Berlin, LNCS 8327, pp. 187 – 198 |
| 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 | 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 |
| 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 | 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 | Colouring AT-free graphs [ACTI85] D. Kratsch, H. Müller Proceedings of ESA 2012 Springer-Verlag, 2012 Berlin, LNCS 7501, pp. 707–718 |
| 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 |
| 2011 | Bicolored independent set and bicliques [ACTI95] J.-F. Couturier, D. Kratsch Proceedings of CTW 2011pp. 130–133 |
| 2011 | Exact algorithms for Kayles [ACTI94] H.L. Bodlaender, D. Kratsch Proceedings of WG 2011Springer- Verlag, 2011Berlin, LNCS 6986, pp. 59–70 |
| 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 |
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 | Enumeration of minimal connected dominating sets and minimal connected vertex covers [COM49] Dieter Kratsch GROW 2015, Aussois, France, 2015 |
| 2015 | Tutorial Input-Sensitive Enumeration [COM48] Dieter Kratsch Leiden, Pays Bas, 2015 |
| 2013 | Journée de l’equipe GAMoC [COM39] Dieter Kratsch «Cliques and Clubs» Orleans, 2013 Université d'Orléans |
| 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 |
| 2012 | Lower bounds in parameterized complexity [COM43] Dieter Kratsch Premières Journées du GT Complexité et Algorithmes, Paris, 2012 |
| 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 | Minimal dominating sets in graphs: enumeration , combinatorial bounds and graph classes » [COM41] Dieter Kratsch Clermont-Ferrand, 2012 JCRAA (Journées Combinatoires Rhone-Alpes Auvergne) |
| 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 |