Julien Baste


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


Teaching

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

Research

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

Since September 2020, I am "Maître de conférences" (assistant 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, treewidth, matchings, multi-objective combinatorial optimization




Publications

Events

Teaching

Internships

Training

Publications

  1. 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 submitted.

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

  3. 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.

  4. Domination versus edge domination
    Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.
    • arXiv version.
    • Short version in Proceedings of 5th Bordeaux Graph Workshop (BGW), 42-44, 2019.
    • Full version to appear in Discrete Applied Mathematics (DAM), 2020.

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

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

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

  8. 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 to appear in Theory of Computing Systems (TOCS), 2020.

  9. Diversity in Combinatorial Optimization
    Julien Baste, Michael R. Fellows, Lars Jaffke, Tomas Masarik, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond.
    • arXiv version.
    • Short version (Part 1/2) in Proceedings of the VIII Latin American Workshop on Cliques in Graphs (LAWCG), 47-47, 2018.
    • Short version (Part 2/2) to appear in the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020.

  10. 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.

  11. Hitting (topological) minors on graphs of bounded treewidth
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
    • arXiv version.
    • 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.
    • Full version (Part 1/3) to appear in SIAM Journal on Discrete Mathematics, 2020.
    • Full version (Part 2/3) in Theoretical Computer Science (TCS), 814: 135-152, 2020.
    • Full version (Part 3/3) in Journal of Computer and System Sciences (JCSS), 109: 56-77, 2020.

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

  13. 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.

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

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

  16. 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.

  17. 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.

  18. 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.

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

  20. 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.

  21. 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
 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  

Teaching

  Year   University   UE code   UE   level   
  2017/2018   Sorbonne Université   PSTL   Projet M1   M1   8H eq. TD 
  192H      4I506   Composants   M1   20H TP 
      4I505   Conception et Pratique de l'Algorithmique    M1   40H TP, 2H cours 
      3I008   Modèles de programmation et interopérabilité des langages   L3   18H TP 
      4I900   Complexité, Algorithmes Randomisés et Approchés   M1   20H TP 
      3I014   Réseaux   L3   38,5H TD 
      2I0I1    Orientation et Insertion Professionnelle   L2   44H TD 
  2016/2017   Université de Montpellier   HLIN102   Du binaire au web   L1   24H TP, 15H TD 
  62H      HLSE305   C2I   APESS   18H TP 
      HLIN101   Introduction à l'algorithmique et à la programmation   L1   4H TD 
  2015/2016   Université de Montpellier   HLIN102   Du binaire au web   L1   22H TP, 14H TD 
  69H      HLSE305   C2I   L2   33H TP 
  2014/2015   Université de Montpellier   HLIN202   Programmation avancée   L1   18H TP 
  69H      HLIN101   Introduction à l'algorithmique et à la programmation   L1   24H TP, 27H TD 

Internships

Training