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. Composing dynamic programming tree-decomposition-based algorithms
    Julien Baste.

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

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

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

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

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

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

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

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

  10. 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) to appear in Journal of Graph Theory, 2018.

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

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

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

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

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

  16. 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, Manuscript Slides
                        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.