Julien Baste


Maître de conférences
(associate professor)
in Université de Lille
email : julien.baste (at) univ-lille.fr


Teaching

at IUT A
Office: 3.47
Tel: +33  3 59 63 22 48

Research

in the ORKAD research team
at CRIStAL
Office: ESPRIT S3.05
Tel: +33  3 28 77 85 78

Since September 2020, I am "Maître de conférences" (associate professor) at Université de Lille in Lille, France. I am teaching computer science at IUT A. I do my research as a member of the ORKAD research team in CRIStAL.

My research interests are: Algorithms, reductions, graph theory, parameterized complexity, multi-objective optimization



PhD opportunity: I am looking for graduate or about-to-graduate student that want to do a PhD on the topic "Parameterized complexity: A tool to handle multiobjective problems. Application to lung cancer detection.", that is at the frontier between parameterized complexity and multi-objective optimization. The description of the PhD can be found here. If you are interested please send an email to Laetitia Jourdan and myself.


Publications

Events

Publications

  1. γ-Cluster Edge Modification Problems
    Antoine Castillon, Julien Baste, Clarisse Dhaenens, Mohammed Haddad, and Hamida Seba.
    • Short version in Proceedings of the 11th International Colloquium on Graph Theory and combinatorics (ICGT), 40, 2022.

  2. Towards hybridization of Multi-Agent simulation and metaheuristics applied to selective deconstruction
    Corentin Juvigny, Julien Baste, Guillaume Lozenguez, Arnaud Doniec, and Laetitia Jourdan.
    • Short version to appear in Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence (SSCI) Proceedings (SSCI), 2022.

  3. Quasi-Clique Mining for Graph Summarization
    Antoine Castillon, Julien Baste, Hamida Seba, and Mohammed Haddad.
    • Short version in Proceedings of the 33rd International Conference on Database and Expert Systems Applications (DEXA), LNCS 13427: 310-315, 2022.

  4. An FPT Algorithm for Spanning, Steiner and Other subTree Problems Parameterized by Treewidth
    Julien Baste and Dimitri Watel.
    • Short version in Proceedings of the 11th International Colloquium on Graph Theory and combinatorics (ICGT), 13, 2022.

  5. Digitalisation de la déconstruction sélective : simulation et optimisation des filières
    Corentin Juvigny, Julien Baste, Guillaume Lozenguez, Arnaud Doniec, and Laetitia Jourdan.
    • Short version in Proceedings of Rencontres des Jeunes Chercheurs en Intelligence Artificielle (RJCIA), 79-81, 2021.
    • Short version to appear in Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), 2022.

  6. A Neighborhood Preserving Graph Compression
    Karima Amrouche, Julien Baste, Mohammed Haddad, Abd Errahmane Kiouche, and Hamida Seba.

  7. Non-monotone target sets for threshold values restricted to 0, 1, and the vertex degree
    Julien Baste, Stefan Ehard, and Dieter Rautenbach.

  8. Acyclic matchings in graphs of bounded maximum degree
    Julien Baste, Maximilian Fürst, and Dieter Rautenbach.
    • arXiv version.
    • Short version in Proceedings of the 26th International Computing and Combinatorics Conference (COCOON), LNCS 12273: 542-553, 2020.
    • Full version in Discrete Mathematics (DM), 345(7): 112885, 2022.

  9. FPT Algorithms for Diverse Collections of Hitting Sets
    Julien Baste, Lars Jaffke, Tomas Masarik, Geevarghese Philip, and Günter Rote.

  10. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
    • arXiv version.
    • Short version in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 951-970, 2020.
    • Full version submitted.

  11. Domination versus edge domination
    Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.

  12. Bounding and approximating minimum maximal matchings in regular graphs
    Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.

  13. Composing dynamic programming tree-decomposition-based algorithms
    Julien Baste.

  14. Linear programming based approximation for unweighted induced matchings — breaking the ∆ barrier
    Julien Baste, Maximilian Fürst, and Dieter Rautenbach.

  15. Minimum Reload Cost Graph Factors
    Julien Baste, Didem Gözüpek, Mordechai Shalom, and Dimitrios M. Thilikos.
    • arXiv version.
    • Short version in Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS 11376: 67-80, 2019.
    • Full version in Theory of Computing Systems (TOCS): 815-838, 2021.

  16. Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
    Julien Baste, Michael R. Fellows, Lars Jaffke, Tomas Masarik, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond.

  17. Temporal matching in link stream: kernel and approximation
    Julien Baste, Bình Minh Bùi Xuân, and Antoine Roux.
    • arXiv version.
    • Short version in Proceedings of the 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW), 163-166, 2018.
    • Full version in Theoretical Computer Science (TCS), 806: 184-196, 2020.

  18. Hitting minors on bounded treewidth graphs. III. Lower bounds
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  19. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  20. Hitting minors on bounded treewidth graphs. I. General upper bounds
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  21. Hitting (topological) minors on graphs of bounded treewidth
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
    • Short version (Part 1/2) in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPICS 89: 4:1-4:12, 2017.
    • Short version (Part 2/2) in Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC), LIPICS 115: 2:1-2:13, 2018.

  22. Contraction-Bidimensionality of geometric intersection graphs
    Julien Baste and Dimitrios M. Thilikos.
    • arXiv version.
    • Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs 89: 5:1-5:13, 2017.
    • Full version in Algorithmica (Algorithmica), 84(2): 510-531, 2022.

  23. Parameterized complexity of finding a spanning tree with minimum reload cost diameter
    Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos.
    • arXiv version.
    • Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs 89: 3:1-3:12, 2017.
    • Full version in Networks (Networks), 75: 259-277, 2020.

  24. Degenerate Matchings and Edge Colorings
    Julien Baste and Dieter Rautenbach.

  25. Uniquely restricted matchings and edge colorings
    Julien Baste, Dieter Rautenbach, and Ignasi Sau.

  26. Ruling out FPT algorithms for Weighted Coloring on forests
    Júlio Araújo, Julien Baste, and Ignasi Sau.
    • arXiv version.
    • Short version in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), EDM 62: 195-200, 2017.
    • Full version in Theoretical Computer Science (TCS), 729: 11-19, 2018.

  27. On the number of labeled graphs of bounded treewidth
    Julien Baste, Marc Noy, and Ignasi Sau.
    • arXiv version.
    • Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 10520: 88-99, 2017.
    • Full version in European Journal of Combinatorics (EJC), 71: 12-21, 2018.

  28. On the Parameterized Complexity of the Edge Monitoring problem
    Julien Baste, Fairouz Beggas, Hamamache Kheddouci, and Ignasi Sau.
    • Full version in Information Processing Letters (IPL), 121: 39-44, 2017.

  29. Parameterized complexity dichotomy for (r,l)-Vertex Deletion
    Julien Baste, Luerbio Faria, Sulamita Klein, and Ignasi Sau.

  30. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
    Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca.
    • arXiv version.
    • Short version in Proceedings of the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM), LNCS 9778: 53-64, 2016.
    • Full version in Bulletin of Mathematical Biology (BMAB), 79(4): 920-938, 2017.

  31. The role of planarity in connectivity problems parameterized by treewidth
    Julien Baste and Ignasi Sau.
    • arXiv version.
    • Short version in Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC), LNCS 8894: 63-74, 2014.
    • Full version in Theoretical Computer Science (TCS), 570: 1-14, 2015.

Events

 Event  Place  From   To
 ICGT2022    ​Montpellier, France    04/07/2022    08/07/2022  
 Third Southwestern German Workshop on Graph Theory    ​Heidelberg, Germany    27/06/2022    01/07/2022  
 ROADEF2022    ​Lyon, France    23/02/2022    25/02/2022  
 Algorithmic Aspects of Temporal Graphs IV    ​Online,    12/07/2021    12/07/2021  
 JGA2019    ​Bruxelles, Belgium    13/11/2019    15/11/2019  
 BGW2019    ​Bordeaux, France    28/10/2019    31/10/2019  
 FraNorAC2019    ​Montpellier, France    19/09/2019    20/09/2019  
 Research meeting    ​Montpellier, France    16/07/2019    18/07/2019  
 GCCR2019    ​Paris, France    09/09/2019    10/09/2019  
 Research meeting    ​Lyon, France    08/07/2019    12/07/2019  
 Seminar    ​Paris, France    22/03/2019    22/03/2019  
 Seminar    ​Evry, France    21/03/2019    21/03/2019  
 Seminar    ​Dijon, France    19/03/2019    19/03/2019  
 Research meeting    ​Grenoble, France    12/03/2019    15/03/2019  
 SOFSEM2019    ​Nový Smokovec, Slovakia    27/01/2019    30/01/2019  
 Research meeting    ​Lyon, France    21/01/2019    25/01/2019  
 Seminar    ​Bordeaux, France    11/01/2019    11/01/2019  
 Research meeting    ​Montpellier, France    08/01/2019    10/01/2019  
 Seminar    ​Marseille, France    07/01/2019    07/01/2019  
 40 Years of Graphs and Algorithms    ​Paris, France    11/10/2018    12/10/2018  
 Seminar    ​Marne-la-Vallée, France    09/10/2018    09/10/2018  
 ALGO2018    ​Helsinki, Finland    20/08/2018    24/08/2018  
 CTW2018    ​Paris, France    18/06/2018    20/06/2018  
 SGT2018    ​Sète, France    11/06/2018    15/06/2018  
 Research meeting    ​Budapest, Hungary    20/05/2018    02/06/2018  
 Research meeting    ​Bergen, Norway    18/03/2018    31/03/2018  
 Recent Advances in Parameterized Complexity    ​Tel Aviv, Israel    03/12/2017    07/12/2017  
 ALGO2017    ​Vienna, Austria    04/09/2017    08/09/2017  
 PCSS2017    ​Vienna, Austria    01/09/2017    03/09/2017  
 WG2017    ​Eindhoven, The Netherlands    21/06/2017    23/06/2017  
 Research meeting    ​Ulm, Germany    30/01/2017    03/02/2017  
 Research meeting    ​Fortaleza, Brazil    21/11/2016    09/12/2016  
 JGA2016    ​Paris, France    16/11/2016    18/11/2016  
 AAIM2016    ​Bergamo, Italy    18/07/2016    20/07/2016  
 Research meeting    ​Istanbul, Turkey    26/06/2016    01/07/2016  
 ÉPIT2016    ​Marseille, France    09/05/2016    13/05/2016  
 JGA2015    ​Orléans, France    04/11/2015    06/11/2015  
 GROW 2015    ​Aussois, France    11/10/2015    15/10/2015  
 Research meeting    ​Lyon, France    07/07/2015    09/07/2015  
 SGT2015    ​Porquerolles, France    18/05/2015    22/05/2015  
 Research meeting    ​Barcelona, Spain    02/05/2015    08/08/2015  
 15èmes JCALM    ​Sophia-Antipolis, France    10/03/2015    11/03/2015  
 International Workshop on Graph Decomposition    ​CIRM, Marseille, France    19/01/2015    23/01/2015  
 JGA 2014    ​Dijon, France    12/11/2014    14/11/2014  
 IPEC'14    ​Wroclaw, Poland    10/09/2014    12/09/2014