Dieter Kratsch
Université de Metz
Laboratoire d'Informatique Théorique et Appliquée
57045 Metz Cedex 01
France
Office Phone: ++ 33 3 87 31 54 44
FAX: ++ 33 3 87 31 53 09
e-mail: kratsch@sciences.univ-metz.fr
URL: http:///www.lita.univ-metz.fr/ppages/kratsch.html
Personal
Born: August 1, 1959 at Altenburg (Germany)School: 1966 - 1978 at Altenburg
Educational Background and Degrees Received
1980 - 1985: Student of Mathematics at the Friedrich-Schiller-University of Jena (Germany)1985: Diplom-Mathematiker (corresponds to M.SC.) ``Über Einschränkungen einiger NP-vollständiger Graphenprobleme auf Permutationsgraphen'' (On the restriction of NP-complete graph problems to permutation graphs)
1989: Promotion (Ph.D. Dissertation), ``Über die Einschränkung NP-vollständiger Graphenprobleme auf Teilklassen chordaler Graphen'' (On the restriction of NP-complete graph problems to subclasses of chordal graphs) in Computer Science (Algorithms); supervisor: Dr. A. Brandstädt
1996: Habilitation, ``The structure of graphs and the design of efficient algorithms'' in Computer Science (Algorithms)
Employment History
1985-1993: Assistant of Dr. G. Wechsung at the Department of Mathematics, Friedrich-Schiller-University of Jena, Germany1993-1994: PostDoc, IRISA Rennes, France; European project ``Capital Humain et Mobilité''
1994-1997: Assistant of Dr. G. Wechsung at the Department of Mathematics and Computer Science, Friedrich-Schiller-University of Jena, Germany
April to September 1997: Guest Professor at the University of Paderborn, Germany
1997-1999: ``Oberassistent'' (C2 in Germany) in the group of Dr. G. Wechsung, Department of Mathematics and Computer Science, Friedrich-Schiller-University of Jena, Germany
1999-present: Full Professeur des universités (corresponds to Full Professor) at the University of Metz, France
Research Interests
Theoretical Computer Science and Discrete Mathematics:-
Algorithms
efficient algorithms, algorithms for special graph classes, exponential time algorithms, approximation algorithms, certifying algorithms, etc. - NP-hard problems
- Structural Graph Theory and Graph Classes
- Partially Ordered Sets
- Reconstruction Problems
Research Grants Received
2001-2002: Project supported by the Region Moselle (France) ``Algorithmique: intutionelle et efficace'' together with L. Colson (Metz)2004: Project AURORA of the association EGIDE (France) ``Separators in graphs: theory and applications'' together with A. Berry (Clermont-Ferrand, France), I. Todinca (Orleans, France), F. Fomin (Bergen, Norway), P. Heggernes (Bergen, Norway) and Y. Villander (Bergen, Norway)
Papers in Refereed Journals
1. A.Brandstädt, D. Kratsch, On the partition of permutations into increasing or decreasing subsequences, Journal of Information and Cybernetic Processes (EIK) 22 (1986), 263--273.2. D. Kratsch, Finding the minimum bandwidth of an interval graph, Information & Computation 74 (1987), 140--158.
3. A.Brandstädt, D. Kratsch, On domination problems for permutation and other graphs, Theoretical Computer Science 54 (1987), 181--198.
4. D. Kratsch, Finding minimum dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Discrete Mathematics 86 (1990), 225--238.
5. P. Damaschke, H. Müller, D. Kratsch, Domination on chordal bipartite and convex graphs, Information Processing Letters 36 (1990), 231--236.
6. P. Erdös, J. Gimbel, D. Kratsch, Extremal results in cochromatic and dichromatic theory, Journal of Graph Theory 15 (1991), 579--585.
7. P. Damaschke, J.S. Deogun, D. Kratsch, G. Steiner, Finding hamiltonian paths in cocomparability graphs using the bump number algorithm, Order 8 (1992), 383--391.
8. H. Bodlaender, D. Kratsch, The complexity of coloring games on perfect graphs, Theoretical Computer Science 106 (1992), 309--326.
9. D. Kratsch, L. Stewart, Domination on cocomparability graphs, SIAM Journal on Discrete Mathematics 6 (1993), 400--417.
10. J. Gimbel, D. Kratsch, L. Stewart, On cocolourings and cochromatic number of graphs, Discrete Applied Mathematics 48 (1994), 111--127.
11. D. Kratsch, L. Hemaaspandra, On the complexity of graph reconstruction, Mathematical Systems Theory 27 (1994), 257--273.
12. D. Kratsch, P. Damaschke, A. Lubiw, Dominating cliques in chordal graphs, Discrete Mathematics 128 (1994), 269--276.
13. D. Kratsch, J.-X. Rampon, A counterexample about poset reconstruction, Order 11 (1994), 95--96.
14. D. Kratsch, J.-X. Rampon, Towards the reconstruction of posets, Order 11 (1994), 317--341.
15. T. Kloks, D. Kratsch, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, Information Processing Letters 55 (1995), 11--16.
16. T. Kloks, D. Kratsch, Treewidth of chordal bipartite graphs, Journal of Algorithms 19 (1995), 266--281.
17. H. Bodlaender, T. Kloks, D. Kratsch, Treewidth and pathwidth of permutation graphs, SIAM Journal on Discrete Mathematics 8 (1995), 606--616.
18. A. Gyarfás, D. Kratsch, J. Lehel, F. Maffray, Minimal non-neighbourhood-perfect graphs, Journal of Graph Theory 21 (1996), 55--66.
19. D. Kratsch, J. Lehel, H. Müller, Toughness, hamiltonicity and split graphs, Discrete Mathematics 150 (1996), 231--245.
20. D. Kratsch, J.-X. Rampon, Width two posets are reconstructible, Discrete Mathematics 162 (1996), 305--310.
21. T. Kloks, D. Kratsch, J. Spinrad, On treewidth and minimum fill-in of asteroidal triple-free graphs, Theoretical Computer Science 175 (1997), 309--335.
22. J.S. Deogun, D. Kratsch, G. Steiner, An approximation algorithm for clustering graphs with dominating diametral path, Information Processing Letters 61 (1997), 121--127.
23. J.S. Deogun, D. Kratsch, G. Steiner, 1-tough cocomparability graphs are hamiltonian, Discrete Mathematics 171 (1997), 99--106.
24. D. Kratsch, T. Kloks, H. Müller, Measuring the vulnerability for classes of intersection graphs, Discrete Applied Mathematics 77 (1997), 259--270.
25. D. Kratsch, L.K. Stewart, Total domination and transformation, Information Processing Letters 63 (1997), 167--170.
26. H. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs. Tuza, Rankings of graphs, SIAM Journal on Discrete Mathematics 11 (1998), 168--181.
27. T. Kloks, D. Kratsch, Listing all minimal separators of a graph, SIAM Journal on Computing 27 (1998), 605--613.
28. H. Bodlaender, T. Kloks, D. Kratsch, H. Müller, Treewidth and minimum fill-in on d-trapezoid graphs, Journal of Graph Algorithms and Applications 2 (1998), no. 5, 1--20.
29. T. Kloks, D. Kratsch, C.K. Wong, Minimum fill-in on circle and circular-arc graphs, Journal of Algorithms 28 (1998), 272--289.
30. D. Kratsch, J.-X. Rampon, Tree-visibility orders, Discrete Mathematics 190 (1998), 163--175.
31. T. Kloks, D. Kratsch, H. Müller, Bandwidth of chain graphs, Information Processing Letters 68 (1998), 313--315.
32. H. Broersma, T. Kloks, D. Kratsch, H. Müller, Independent sets in asteroidal triple-free graphs, SIAM Journal on Discrete Mathematics, 12 (1999), 267--287.
33. T. Kloks, D. Kratsch, H. Müller, Approximating the bandwidth for asteroidal triple-free graphs, Journal of Algorithms 32 (1999), 41--57.
34. J.S. Deogun, T. Kloks, D. Kratsch, H. Müller, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Applied Mathematics 98 (1999), 39--63.
35. D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics 99 (2000), 111--123.
36. D. Bauer, G.Y. Katona, D. Kratsch, H.J. Veldman, Chordality and 2-factors in tough graphs, Discrete Applied Mathematics 99 (2000), 323--330.
37. H. Broersma, O. Koppius, H. Tuinstra, A. Huck, T. Kloks, D. Kratsch, H. Müller, Degree-preserving trees, Networks 35 (2000), 26--39.
38. T. Kloks, D. Kratsch, H. Müller, Finding and counting small induced subgraphs efficiently, Information Processing Letters 74 (2000), 115--121.
39. L. Babel, T. Kloks, J. Kratochvíl, D. Kratsch, H. Müller, S. Olariu, Efficient algorithms for graphs with few P4's, Discrete Applied Mathematics 235 (2001), 29--51.
40. T. Kloks, D. Kratsch, H. Müller, On the structure of graphs with bounded asteroidal number, Graphs and Combinatorics 17 (2001), 295--306.
41. H.J. Broersma, T. Kloks, D. Kratsch, H. Müller, A generalization of AT-free graphs and a generic algorithm for solving triangulation problems, Algorithmica 32 (2002), 594--610.
42. J.S. Deogun, D. Kratsch, Dominating pair graphs, SIAM Journal on Discrete Mathematics 15 (2002), 353--366.
43. H. Bodlaender, D. Kratsch, Kayles and nimbers, Journal of Algorithms, 42 (2002), 106--119.
44. H. Hempel, D. Kratsch, On claw-free asteroidal triple-free graphs, Discrete Applied Mathematics 121 (2002), 155--180.
45. D. Kratsch, L.K. Stewart, Approximating bandwidth by mixing layouts of interval graphs, SIAM Journal on Discrete Mathematics 15 (2002), 435--449.
46. F. Fomin, D. Kratsch, J.-C. Novelli, Approximating minimum cocolourings, Information Processing Letters 84 (2002), pp. 285--290.
47. F. Fomin, D. Kratsch, H. Müller, On the domination search number, Discrete Applied Mathematics 127 (2003), pp. 565--580.
48. E. Prisner, D. Kratsch, H.-O. Le, H. Müller, D. Wagner, Additive tree spanners, SIAM Journal on Discrete Mathematics 17 (2003) pp. 332--340.
49. F. Fomin, D. Kratsch, H. Müller, Algorithms for graphs with small octopus, Discrete Applied Mathematics 134 (2004) pp. 105--128.
50. V. Bouchitté, I. Todinca, D. Kratsch, H. Müller, On treewidth approximations, Discrete Applied Mathematics. 136 (2004) pp. 183--196.
51. A. Brandstädt, D. Kratsch, On the structure of (P5,gem)-free graphs, Discrete Applied Mathematics 145 (2005) pp. 155--166.
Chapter in a Monograph
1. D. Kratsch, Algorithms, Domination in Graphs: Advanced Topics, Chapter 8, T. Haynes, S. Hedetniemi, P. Slater, (eds.), Series: Pure and Applied Mathematics, Volume: 209, Marcel Dekker Inc., 1998, pp. 191--231.Papers in Refereed Proceedings2
1. A. Brandstädt, D. Kratsch, On the restriction of some NP--complete graph problems to permutation graphs, Proceedings of FCT'85, L. Budach, (ed.), Springer-Verlag, Berlin, 1985, LNCS 199, pp. 53--62.2. D. Kratsch, L. Hemachandra, On the complexity of graph reconstruction, Proceedings of FCT'91, L. Budach, (ed.), Springer-Verlag, Berlin, 1991, LNCS 529, pp. 318--328.
3. T. Kloks, D. Kratsch, Treewidth of chordal bipartite graphs, Proceedings of STACS'93, P. Enjalbert, A. Finkel, K.W. Wagner, (eds.), Springer-Verlag, Berlin, 1993, LNCS 665, pp. 80--89.
4. H. Bodlaender, T. Kloks, D. Kratsch, Treewidth and pathwidth of permutation graphs, Proceedings of ICALP'93, A. Lingas, R. Karlsson, S. Carlsson, (eds.), Springer-Verlag, Berlin, 1993, LNCS 700, pp. 114--125.
5. T. Kloks, H. Bodlaender, H. Müller, D. Kratsch, Computing treewidth and minimum fill-in: all you need are the minimal separators, Proceedings of ESA'93, T. Lengauer, (ed.), Springer-Verlag, 1993, Berlin, LNCS 726, pp. 260--271.
6. J.S. Deogun, T. Kloks, D. Kratsch, H. Müller, On vertex ranking for permutation and other graphs, Proceedings of STACS'94, P. Enjalbert, E.W. Mayr, K.W. Wagner, (eds.), Springer-Verlag, 1994, Berlin, LNCS 775, pp. 747--758.
7. T. Kloks, D. Kratsch, Finding all minimal separators of a graph, Proceedings of STACS'94, P. Enjalbert, E.W. Mayr, K.W. Wagner, (eds.), Springer-Verlag, 1994, Berlin, LNCS 775, pp. 759--768.
8. T. Kloks, D. Kratsch, H. Müller, Dominoes, Proceedings of WG'94, E.W. Mayr, G. Schmidt, G. Tinhofer, (eds.), Springer-Verlag, 1995, Berlin, LNCS 903, pp. 106--120.
9. H. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs. Tuza, Rankings of graphs, Proceedings of WG'94, E.W. Mayr, G. Schmidt, G. Tinhofer, (eds.), Springer-Verlag, 1995, Berlin, LNCS 903, pp. 292--304.
10. T. Kloks, D. Kratsch, H. Müller, Approximating the bandwidth for asteroidal triple-free graphs, Proceedings of ESA'95, P. Spirakis, (ed.), Springer-Verlag, 1995, Berlin, LNCS 979, pp. 434--447.
11. T. Kloks, D. Kratsch, H. Müller, Finding and counting small induced subgraphs efficiently, Proceedings of WG'95, M. Nagl, (ed.), Springer-Verlag, 1995, Berlin, LNCS 1017, pp. 14--23.
12. J. Deogun, D. Kratsch, Diametral path graphs, Proceedings of WG'95, M. Nagl, (ed.), Springer-Verlag, 1995, Berlin, LNCS 1017, pp. 344--357.
13. T. Kloks, D. Kratsch, C.K. Wong, Minimum fill-in of circle and circular-arc graphs, Proceedings of ICALP'96, F. Meyer auf der Heide, B. Monien, (eds.), Springer-Verlag, 1996, Berlin, LNCS 1099, pp. 256--267.
14. H. Broersma, T. Kloks, D. Kratsch, H. Müller, Independent sets in asteroidal triple-free graphs, Proceedings of ICALP'97, P. Degano, R. Gorrieri, A. Marchetti-Spaccamela, (eds.), Springer-Verlag, 1997, Berlin, LNCS 1256, pp. 760--770.
15. T. Kloks, D. Kratsch, H. Müller, Asteroidal sets in graphs, Proceedings of WG'97, R. Möhring, (ed.), Springer-Verlag, 1997, Berlin, LNCS 1335, pp. 229--241.
16. H.J. Broersma, A. Huck, T. Kloks, O. Koppius, D. Kratsch, H. Müller, H. Tuinstra, Degree-preserving forests, Proceedings of MFCS'98, L. Brim, J. Gruska, J. Zlatuska, (eds.), Springer-Verlag, 1998, Berlin, LNCS 1450, pp. 713--721.
17. H.J. Broersma, T. Kloks, D. Kratsch, H. Müller, A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-in and vertex ranking, Proceedings of WG'98, J. Hromkovic, O. Sykora, (eds.), Springer-Verlag, 1998, Berlin, LNCS 1517, pp. 88--99.
18. D. Kratsch, L.K. Stewart, Approximating bandwidth by mixing layouts of interval graphs, Proceedings of STACS'99, C. Meinel, S. Tison, (eds.), Springer-Verlag, 1999, Berlin, LNCS 1563, pp. 248--258.
19. H. Hempel, D. Kratsch, On claw-free asteroidal triple-free graphs, Proceedings of WG'99, Springer-Verlag, 1999, Berlin, LNCS 1665, pp. 377--390.
20. F. Fomin, D. Kratsch, H. Müller, On the domination search number, Proceedings of WG'2000, Springer-Verlag, 2000, Berlin, LNCS 1928, pp. 161--171.
21. T. Kloks, D. Kratsch, Y. Le Borgne, H. Müller, Bandwidth of split and circular permutation graphs, Proceedings of WG'2000, Springer-Verlag, 2000, Berlin, LNCS 1928, pp. 243--254.
22. F. Fomin, D. Kratsch, J.-C. Novelli, Approximating minimum cocolourings, Proceedings of FCT'2001, Springer-Verlag, 2001, Berlin, LNCS 2138, pp. 118--125.
23. D. Kratsch, R. McConnell, K. Mehlhorn, J. Spinrad, Certifying algorithms to recognize interval and permutation graphs, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003), pp. 158--167.
24. D. Kratsch, J. Spinrad, Between O(nm) and O(na), Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003), pp. 709--716.
25. H.L. Bodlaender, A. Brandstädt, D. Kratsch, M. Rao, J. Spinrad, Linear time algorithms for some NP-complete problems on (P5,gem)-free graphs, Proceedings of FCT 2003, Springer-Verlag, 2003, Berlin, LNCS 2751, pp. 61--72.
26. D. Kratsch, H. Müller, I. Todinca, Feedback vertex set and longest induced path on AT-free graphs, Proceedings of WG'2003, Springer-Verlag, 2003, Berlin, LNCS 2880, pp. 309--321.
27. F. Fomin, D. Kratsch, I. Todinca, Exact (exponential) algorithms for treewidth and min fill-in, Proceedings of ICALP'2004, Springer-Verlag, 2004, Berlin, LNCS 3124, pp. 568--580.
Papers accepted for Publication in Refereed Proceedings
1. F. Fomin, D. Kratsch, G. Woeginger, Exact (exponential) algorithms for the dominating set problem, accepted for Proceedings of WG 2004.Publications in Refereed Books
1. O. Favaron, D. Kratsch, Ratios of domination parameters, Advances in Graph Theory, V. Kulli, (ed.), Vishwa International Publications, India, 1991, pp. 173--182.Submitted Papers
1. D. Kratsch, J.P. Spinrad, R. Sritharan, A new characterization of HH-free graphs.2. T. Kloks, D. Kratsch, C.M. Lee, J. Liu, Improved bottleneck domination algorithms.
3. D. Kratsch, J. Spinrad, Minimal fill in o(n3) time.
Special Volumes
1. Second International Colloquium "Journées de l'Informatique Messine". [Second International Colloquium "Computer Science at Metz"] Papers from the Colloquium on Graph Algorithms (JIM '2000) held at the Université de Metz, Metz, May 22--24, 2000. Edited by D. Kratsch. Discrete Appl. Math. 131 (2003), no. 1. Elsevier Science B.V., Amsterdam, 2003. pp. iii--x and 1--252.Thesis
1. Diploma Thesis, ``Über Einschränkungen einiger NP-vollständiger Graphenprobleme auf Permutationsgraphen'' (On the restriction of some NP-complete problems to permutation graphs), Jena, Germany, 1985.2. Dissertation Thesis, ``Über die Einschränkung NP-vollständiger Graphenprobleme auf Teilklassen chordaler Graphen'' (On the restriction of NP-complete graph problems to subclasses of chordal graphs), Jena. Germany, 1989.
3. Habilitation Thesis, The structure of graphs and the design of efficient algorithms, Jena, Germany, 1996.
Graduate Students Supervised:
Diploma Theses: T. Wolle, D. Meister, E. Köhler, P. Damaschke and othersThésards (corresponds to Ph.D. students): M. Rao (started in 2002), M. Liedloff (started in 2004)
Further Professional Activities
Organizer of the following conferences:
Second International Colloquium "Journées de l'Informatique Messine" (JIM'2000), Metz, 2000.31st International Conference on Graph-Theoretic Concepts in Computer Science (WG'2005), Metz, 2005.
Member of the following conference program committees:
WG'2001 (Boltenhagen, Germany, 2001)MFCS'2004 (Prague, Czech Republic, 2004)
WG'2005 (Metz, France, 2005)
Referee for journals such as:
Journal of the ACMSIAM Journal on Computing
SIAM Journal on Discrete Mathematics
Discrete Mathematics
Discrete Applied Mathematics
Journal of Algorithms
Algorithmica
Theoretical Computer Science
Networks
Acta Informatica
Journal of Heuristics
Information Processing Letters.
Referee for international conferences such as:
SODA (Symposium on Discrete Algorithms)ESA (European Symposium on Algorithms)
STACS (Symposium on Theoretical Aspects of Computer Sciences)
MFCS (Mathematical Foundations of Computer Sciences)
WG (Workshop on Graph-Theoretic Concepts in Computer Science)