some keywords concerning my current research areas :
- algorithms, exact algorithms, polynomial-time and exponential-time algorithms, fixed parameter algorithms
- running-time analysis
- combinatorial bounds and enumerative problems
- graphs, graph classes,
- NP-hard problems
- domination, treewidth, labelling ...
as a PhD student :From october 2004 to december 2007, I prepared a PhD thesis in computer sciences at the University of Metz (France). The subject of my thesis was "Exact exponential-time algorithms for NP-hard problems" and my advisor was Prof. Dieter Kratsch.
The aim of my research is to find exact algorithms for solving some NP-hard problems. Since it seems really unlikely to obtain polynomial time algorithms for solving this kind of problems (unless P=NP), it is a natural approach to ask whether we can find some "fast" exponential-time algorithms for these problems. Consequently, we hope to find algorithms whose running time is bounded by a function of the form c^n, where c is a small constant (the closer to 1, the better it is).
Some references concerning my works can be found here.
during my DEA (Master's degree) :I hold a Master's degree in computer sciences ("Diplôme d'Etudes Approfondies Informatique de Lorraine"). This diploma, accredits by the University of Nancy 1 (France), Nancy 2(France), The "Institut National Polytechnique de Lorraine" (France), and the Université of Metz(France), offers four special subjects one of which is "algorithmics".
This was a research training period of six months under Prof. Dieter Kratsch at the LITA (university of Metz).
The aim of this training period was to study the Roman Domination problem. That is a variant of the well-know problem of domination in graphs. This problem was shown to be NP-complete and our goal was to verify if it is possible (as for the usual domination problem) to obtain polynomial time algorithms when roman domination was restricted to some graph classes or to show that the problems remains NP-hard on these graph classes. Moreover, we obtained some results concerning the fixed-parameterized complexity of Roman Domination (similarly to the domination problem) and an exponential-time algorithm.
during my Maîtrise (four-year university degree) :I did a research projet (memoire) on NP-complete problems under Prof. Dieter Kratsch. This subject was not really taught in regular courses and this work gave me the possibility to study this important subject.
A large number of problems, both of theoretical and practical importance, are NP-complete. What are the caracteristics of this problems ? How to show that a problem is NP-complete ? I studied some chapters of the book due to M.R. Garey et D.S. Johnson (Computers and Intractability : A Guide to the Theory of NP-Completeness), and also some of the one due to C. Papadimitriou (Computational Complexity). In particular, I studied how to prove NP-completeness of particular problems using a polynomial-time reduction.