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. Bounding and approximating minimum maximal matchings in regular graphs
    Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, and Dieter Rautenbach.

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

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

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

  5. Diversity in Combinatorial Optimization
    Julien Baste, Michael R. Fellows, Lars Jaffke, Tomas Masarik, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond.

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

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

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

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

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

  11. Uniquely restricted matchings and edge colorings
    Julien Baste, Dieter Rautenbach, and Ignasi Sau.
    • arXiv version.
    • Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 10520: 100-112, 2017.
    • Full version (Part 2/2) to appear in Discrete Applied Mathematics, 2019.
    • Full version (Part 1/2) in Journal of Graph Theory, 91(3): 251-258, 2019.

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

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

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

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

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

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