Cette page utilise des feuilles de style en cascade. Si vous arrivez à lire ce message, c'est que CSS ou javascript ne sont pas activés. L'affichage de la page sera donc différent de ce qui est prévu.

List of publications

Publications in Refereed Journals || Publications in Proceedings of Conferences || International Workshops || National Conferences || Technical Reports || Theses


Publications in Refereed Journals :


  1. Dieter Kratsch, Mathieu Liedloff :
    An Exact Algorithm for the Minimum Dominating Clique Problem,
    Theoretical Computer Science 385 (2007), pp. 226-240.

  2. Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng :
    Efficient algorithms for Roman domination on some classes of graphs,
    Discrete Applied Mathematics 156 (18) (2008), pp. 3400-3415.

  3. Mathieu Liedloff :
    Finding a dominating set on bipartite graphs,
    Information Processing Letters 107 (2008), pp. 154-157.

  4. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff :
    Sort and search: Exact algorithms for generalized domination,
    Information Processing Letters 109 (2009), pp. 795-798.

  5. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca :
    Exponential time algorithms for the minimum dominating set problem on some graph classes,
    ACM Transactions on Algorithms 6 (2009), article 9.

  6. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh :
    Iterative Compression and Exact Algorithms,
    Theoretical Computer Science 411 (2010), pp. 1045-1053.

  7. Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff :
    Exact exponential-time algorithms for finding bicliques,
    Information Processing Letters 111 (2010), pp. 64-67.

  8. Frédéric Havet, Martin Klazar, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff :
    Exact algorithms for L(2,1)-labeling of graphs,
    Algorithmica 59 (2) (2011), pp. 169-194.

  9. 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), pp. 252-273.

  10. Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith :
    An exact algorithm for the Maximum Leaf Spanning Tree problem,
    Theoretical Computer Science 412 (45) (2011), pp. 6290-6302.

  11. Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk :
    Breaking the 2^n-barrier for Irredundance: Two lines of attack,
    Journal of Discrete Algorithms 9 (3) (2011), pp. 214-230.

  12. Faisal Abu-Khzam, Amer Mouawad, Mathieu Liedloff :
    An exact algorithm for connected red-blue dominating set,
    Journal of Discrete Algorithms 9 (3) (2011), pp. 252-262.

  13. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff :
    On Independent Sets and Bicliques in Graphs,
    Algorithmica 62 (3-4) (2012), pp. 637-658.

  14. Serge Gaspers, Mathieu Liedloff :
    A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set,
    Discrete Mathematics and Theoretical Computer Science, 14:1 (2012), pp. 29-42.

  15. Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff :
    Exact and Parameterized Algorithms for Max Internal Spanning Tree,
    Algorithmica 65 (1) (2013), pp. 95-128.

  16. Konstanty Junosza-Szaniawski, Jan Kratochvil, Pawel Rzazewski :
    Determining the L(2,1)-Span in Polynomial Space,
    Discrete Applied Mathematics 161 (13-14) (2013), pp. 2052-2061.

  17. Jean-Francois Couturier, Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Artem Pyatkin :
    Colorings With Few Colors: Counting, Enumeration and Combinatorial Bounds,
    Theory of Computing Systems 52 (4) (2013), pp. 645-667.

  18. Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, Pawel Rzazewski :
    Fast exact algorithm for L(2,1)-labeling of graphs,
    Theoretical Computer Science 505 (2013), pp. 42-54.

  19. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    On an extension of the Sort & Search method with application to scheduling theory,
    Theoretical Computer Science 511 (2013), pp. 13-22.

  20. Mathieu Liedloff, Ioan Todinca, Yngve Villanger :
    Solving Capacitated Dominating Set by using covering by subsets and maximum matching,
    Discrete Applied Mathematics 168 (2014), pp. 60-68.

  21. Frédéric Havet, Andrew D. King, Mathieu Liedloff, Ioan Todinca :
    (Circular) backbone colouring: Forest backbones in planar graphs,
    Discrete Applied Mathematics 169 (2014), pp. 119-134.

  22. Serge Gaspers, Mathieu Liedloff, Maya Jakobine Stein, Karol Suchan :
    Complexity of splits reconstruction for low-degree trees,
    Discrete Applied Mathematics 180 (2015), pp. 89-100.

  23. Jean-François Couturier, Romain Letourneur, Mathieu Liedloff :
    On the number of minimal dominating sets on some graph classes,
    Theoretical Computer Science 562 (2015), pp. 634-642.

  24. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider :
    On Finding Optimal Polytrees,
    to appear in Theoretical Computer Science.



Book Chapters :


  1. Christophe Lenté, Mathieu Liedloff, Vincent T'kindt, Ioan Todinca :
    Algorithmes modérément exponentiels pour problèmes NP-difficiles,
    Informatique Mathématique une photographie en 2015, Chapter 2, pp. 47-85.
    Nicolas Ollinger (Editor), CNRS Editions, 2015, ISBN: 978-2-271-08791-1
    .



Publications in Proceedings of Conferences :


  1. Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng :
    Roman Domination over Some Graph Classes,
    Proceedings of WG 2005. Lecture Notes in Computer Science Vol. 3787 (pp. 103-114), Springer-Verlag.

  2. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff :
    Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes,
    Proceedings of SWAT 2006. Lecture Notes in Computer Science Vol. 4059 (pp. 148-159), Springer-Verlag.

  3. Dieter Kratsch, Mathieu Liedloff :
    An Exact Algorithm for the Minimum Dominating Clique Problem,
    Proceedings of IWPEC 2006. Lecture Notes in Computer Science Vol. 4169 (pp. 130-141), Springer-Verlag.

  4. Serge Gaspers, Mathieu Liedloff :
    A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs,
    Proceedings of WG 2006. Lecture Notes in Computer Science Vol. 4271 (pp. 78-89), Springer-Verlag.

  5. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvil, Dieter Kratsch, Mathieu Liedloff :
    Branch and Recharge: Exact algorithms for generalized domination,
    Proceedings of WADS 2007. Lecture Notes in Computer Science Vol. 4619 (pp. 508-519), Springer-Verlag.

  6. Jan Kratochvil, Dieter Kratsch, Mathieu Liedloff :
    Exact algorithms for L(2,1)-labeling of graphs,
    Proceedings of MFCS 2007. Lecture Notes in Computer Science Vol. 4708 (pp. 513-524), Springer-Verlag.

  7. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff :
    On Independent Sets and Bicliques in Graphs,
    Proceedings of WG 2008. Lecture Notes in Computer Science Vol. 5344 (pp. 171-182), Springer-Verlag.

  8. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh :
    Iterative Compression and Exact Algorithms,
    Proceedings of MFCS 2008. Lecture Notes in Computer Science Vol. 5162 (pp. 335-346), Springer-Verlag.

  9. Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith :
    An exact algorithm for the Maximum Leaf Spanning Tree problem,
    Proceedings of IWPEC 2009. Lecture Notes in Computer Science Vol. 5917 (pp. 161-172), Springer-Verlag.

  10. Faisal Abu-Khzam, Amer Mouawad, Mathieu Liedloff :
    An Exact Algorithm for Connected Red-Blue Dominating Set,
    Proceedings of CIAC 2010. Lecture Notes in Computer Science Vol. 6078 (pp. 25-36), Springer-Verlag.

  11. Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith :
    A Parameterized Route to Exact Puzzles: Breaking the 2^n-barrier for irredundancy,
    Proceedings of CIAC 2010. Lecture Notes in Computer Science Vol. 6078 (pp. 311-322), Springer-Verlag.

  12. Mathieu Liedloff, Ioan Todinca, Yngve Villanger :
    Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching,
    Proceedings of WG 2010. Lecture Notes in Computer Science Vol. 6410 (pp. 88-99), Springer-Verlag.

  13. Konstanty Junosza-Szaniawski, Jan Kratochvil, Mathieu Liedloff, Peter Rossmanith, Pawel Rzazewski :
    Fast Exact Algorithm for L(2,1)-Labeling of Graphs,
    Proceedings of TAMC 2011. Lecture Notes in Computer Science Vol. 6648 (pp. 82-93), Springer-Verlag.

  14. Serge Gaspers, Mathieu Liedloff, Maya Stein, Karol Suchan :
    Complexity of Splits Reconstruction for Low-Degree Trees,
    Proceedings of WG 2011. Lecture Notes in Computer Science Vol. 6986 (pp. 167-178), Springer-Verlag.

  15. Konstanty Junosza-Szaniawski, Jan Kratochvil, Pawel Rzazewski :
    Determining the L(2,1)-Span in Polynomial Space,
    Proceedings of WG 2012. Lecture Notes in Computer Science Vol. 7551 (pp. 126-137), Springer-Verlag.

  16. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider :
    On Finding Optimal Polytrees,
    Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2012), Proceedings of AAAI 2012 (pp. 750-756).

  17. Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger :
    Treewidth and Pathwidth Parameterized by the Vertex Cover Number,
    Proceedings of WADS 2013. Lecture Notes in Computer Science Vol. 8037 (pp. 232-243), Springer-Verlag.

  18. Mathieu Chapelle, Manfred Cochefert, Jean-François Couturier, Dieter Kratsch, Mathieu Liedloff, Anthony Perez :
    Exact Algorithms for Weak Roman Domination,
    Proceedings of IWOCA 2013. Lecture Notes in Computer Science Vol. 8288 (pp. 81-93), Springer-Verlag.

  19. Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre-Barba, Ioan Todinca :
    Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques,
    Proceedings of SWAT 2014. Lecture Notes in Computer Science Vol. 8503 (pp. 182-193), Springer-Verlag.

  20. Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff :
    Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size,
    Proceedings of IPEC 2014. Lecture Notes in Computer Science Vol. 8894 (pp. 147-158), Springer-Verlag.

  21. Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pawel Rzazewski :
    Fixing Improper Colorings of Graphs,
    Proceedings of SOFSEM 2015. Lecture Notes in Computer Science Vol. 8939 (pp. 266-276), Springer-Verlag.

  22. Dieter Kratsch, Mathieu Liedloff, Daniel Meister :
    End-Vertices of Graph Search Algorithms,
    to appear in Proceedings of CIAC 2015.

  23. Mathieu Liedloff, Pedro Montealegre, Ioan Todinca :
    Beyond classes of graphs with "few" minimal separators: FPT results through potential maximal cliques,
    to appear in Proceedings of WG 2015.



International Workshops :


  1. Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Daniel Raible :
    Exact exponential-time algorithms for finding bicliques in a graph,
    Proceedings of CTW 2009. Ecole Polytechnique and CNAM (pp. 205-209).

  2. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Exponential-time algorithms for scheduling problems,
    Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011).

  3. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Sort & Search Exponential-Time Algorithms for Scheduling Problems,
    Proceedings of Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2011) (pp. 523-528).

  4. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider :
    Towards Finding Optimal Polytrees,
    NIPS Workshop on Discrete Optimization in Machine Learning (DISCML 2011).

  5. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Scheduling parallel machines with exponential algorithms,
    International Workshop on Approximation, Parameterized and EXact algorithms (APEX 2012).

  6. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Scheduling parallel machines with exponential algorithms,
    13th International Conference on Project Management and Scheduling (PMS 2012) (pp. 203-206).

  7. Jean-François Couturier, Mathieu Liedloff :
    A tight bound on the number of minimal dominating sets in split graph,
    Proceedings of CTW 2013 (pp. 67-70).

  8. Vincent T'Kindt, Christophe Lenté, Mathieu Liedloff :
    A Study of worst-case complexity for parallel machine scheduling problems based on an extension of the Sort & Search method,
    Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2013).

  9. Jean-François Couturier, Romain Letourneur, Mathieu Liedloff :
    On the Number of Minimal Dominating Sets on Cobipartite and Interval Graphs,
    9th International colloquium on graph theory and combinatorics (ICGT 2014).

  10. Lei Shang, Christophe Lenté, Mathieu Liedloff, Vincent T'Kindt :
    An exponential dynamic programming algorithm for the 3-machine flowshop scheduling problem to minimize the makespan,
    Proceedings of Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2015).



National Conferences :


  1. Christophe Lenté, Mathieu Liedloff, Emmanuel Neron, Ameur Soukhal, Vincent T'Kindt :
    Complexité d'algorithmes exponentiels : application au domaine de l'ordonnancement,
    11ième congrès de la Société Francaise de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010).

  2. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Algorithmes Exponentiels Pour Des Problèmes D'Ordonnancement à Une Machine Et Machines Parallèles,
    12ième congrès de la Société Francaise de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011).

  3. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Complexité au pire des cas d'algorithmes exponentiels pour des problèmes de séquencement,
    13ième congrès de la Société Francaise de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012).

  4. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Généralisation de la méthode Trier et Chercher : application à des problèmes à machines parallèles,
    13ième congrès de la Société Francaise de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012).



Technical Reports :


  1. Ton Kloks, Mathieu Liedloff, Jiping Liu, Sheng-Lung Peng :
    Roman domination in some special classes of graphs,
    TR-MA-04-01, Nov. 2004, University of Lethbridge, Alberta, Canada.

  2. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff :
    Exponential time algorithms for the minimum dominating set problem on some graph classes,
    Report No 322, April 2006, Department of Informatics, University of Bergen, Bergen, Norway.

  3. Serge Gaspers, Mathieu Liedloff :
    A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs,
    Report No 344, January 2007, Department of Informatics, University of Bergen, Bergen, Norway.

  4. Frédéric Havet, Martin Klazar, Jan Kratochvil, Dieter Kratsch, Mathieu Liedloff :
    Exact algorithms for L(2,1)-labeling of graphs,
    KAM-DIMATIA Series 2008-875, July 2008, Charles University, Prague, Czech Republic.

  5. Frédéric Havet, Martin Klazar, Jan Kratochvil, Dieter Kratsch, Mathieu Liedloff :
    Exact algorithms for L(2,1)-labeling,
    Research Report 6587, July 2008, INRIA, Sophia Antipolis, France.

  6. 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,
    Computing Research Repository, CoRR abs/0909.4224, September 2009.

  7. Serge Gaspers, Mathieu Liedloff :
    A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set,
    Computing Research Repository, CoRR abs/1009.1381, September 2010.

  8. Serge Gaspers, Mathieu Liedloff, Maya Stein, Karol Suchan :
    Complexity of Splits Reconstruction for Low-Degree Trees,
    Computing Research Repository, CoRR abs/1007.1733, July 2010 / October 2011.

  9. Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider :
    On Finding Optimal Polytrees,
    Computing Research Repository, CoRR abs/1208.1692, August 2012.

  10. Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger :
    TREEWIDTH and PATHWIDTH parameterized by vertex cover,
    Computing Research Repository, CoRR abs/1305.0433, May 2013.

  11. Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent T'Kindt :
    Exponential Algorithms for Scheduling Problems,
    Research Report 300, February 2014, Ecole Polytechnique de l'Université de Tours, Département Informatique, Laboratoire d'Informatique, EA 6300, ERL CNRS OC 6305, France.

  12. Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre-Barba, Ioan Todinca :
    Algorithms parameterized by vertex cover and modular width, through potential maximal cliques,
    Computing Research Repository, CoRR abs/1404.3882, April 2014.



Theses :


  1. Mathieu Liedloff :
    Problèmes NP-complets : introduction au domaine et preuves de NP-complétude,
    Thesis of Maîtrise, mai 2003. Advisor: Prof. Dieter Kratsch, University of Metz (France).

  2. Mathieu Liedloff :
    Domination Romaine,
    Master Thesis (DEA), june 2004. Advisor: Prof. Dieter Kratsch, LITA, University of Metz (France).

  3. Mathieu Liedloff :
    Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : domination, variantes et généralisations,
    Ph.D. thesis, december 2007. Advisor: Prof. Dieter Kratsch, LITA, University of Metz (France).