Dr. Julien Baste

I am currently a post-doc at:

Universität Ulm
Institut für Optimierung und Operations Research
Helmholtzstraße 18
89081 Ulm

Office: 1.48
Tel: +49  731 5023636
Email: Julien.baste (at) uni-ulm.de

Research interest: Algorithms, reductions, graph theory, parameterized complexity,  treewidth, matchings.

Julien Baste

Publications

Events

Teaching

Internships

Training

Publications

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

  2. 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 to appear in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.

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

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

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

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

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

  8. 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 in Proceedings of the VIII Latin American Workshop on Cliques in Graphs (LAWCG), 47-47, 2018.
    • Short version (Part 2/2) submitted.

  9. 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), In press, 2019.

  10. 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) submitted.
    • Full version (Part 2/3) submitted.
    • Full version (Part 3/3) to appear in Journal of Computer and System Sciences, 2019.

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

  12. 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 to appear in Networks (Networks), 2018.

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

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

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

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

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

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

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

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

  • Spring 2014 : Internship of five months in Prague in Tcheque Republic.
  • Autumn 2014 : Internship in bioinformatics in Rennes in France. Poster.
  • Spring 2013 : Internship of five months in AlGCo in Montpellier in France. Master thesis.
  • Spring 2012 : Internship of five months in Bergen in Norway. Internship report.

Training

  • 2014-2017 : Ph.D Student in the AlGCo team at LIRMM in Montpellier in France.
                        The thesis, Treewidth: algorithmic, combinatorial, and practical aspects, ManuscriptSlides
                        was supervised by Ignasi Sau, and Dimitrios Thilikos and
                        was reviewed by Petr Golovach, Marcin Pilipczuk, and Ioan Todinca.
                        The jury was chaired by Vincent Berry.
                        The thesis was defended on September, 22nd, 2017.
  • 2012-2013 : Second year of the MRI Master at ENS Cachan Bretagne in Rennes.
  • 2011-2012 : First year of the MPRI Master at ENS Cachan near Paris.
  • 2010-2011 : Degree at ENS Cachan near Paris.
  • 2008-2010 : Two years of training school at Lycée Saint Louis in Paris. Preparation of the ENS Cachan entrance exam.
  • 2008 : Baccalaureate at Lycée Évariste Gallois in Sartrouville.