Mathilde Vernet

Université Du Havre · UFR Sciences et Techniques · 25 rue Philippe Lebon · BP 1123 · 76063 Le Havre Cedex · mathilde.vernet@univ-lehavre.fr

I have a PhD in computer science and I was suppervised by Éric Sanlaville and Yoann Pigné at LITIS Lab (RI2C team), in Le Havre. I am currently a research and teaching assistant at Université Le Havre Normande. In my research, I focus on optimization in temporal networks. I consider graphs in which vertices, arcs, labels might be time dependent. The main goal is to design efficient algorithms, both theoretically and practically, to solve optimization problems on such graphs.

Keywords: dynamic graph, algorithm, optimization


Upcoming events

Nothing to annouce yet...


Positions

Reasearch and Teaching assistant / ATER

LITIS Laboratory, Université Le Havre Normandie, Le Havre, France
Sept. 2020 - Aug. 2021

Doctoral fellowship

LITIS Laboratory, Université Le Havre Normandie, Le Havre, France
Sept. 2017 - Aug. 2020

Publications

Journal Article Mathilde Vernet, Maciej Drozdowski, Yoann Pigné, Éric Sanlaville, "A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs", In Discrete Applied Mathematics, 2020. 10.1016/j.dam.2019.12.012.


Main Scientific Communications

Journées Graphes et Algorithmes 2020

Complexité du problème de Steiner dynamique

On the complexity of the dynamic Steiner problem. Presentation on the complexity of the dynamic Steiner problem during the annual meeting of French working groups on graphs and algorithms. This work was made with Stefan Balev, Yoann Pigné and Éric Sanlaville.

Visit JGA 2020 page here.

See abstract of this presentation (in french) here and the presentation slides here.

November 2020, Sophia Antipolis, France (Online)

AlgoTel Conference 2020

Détection de composantes connexes persistantes non dominées dans un graphe dynamique

Non-dominated Persistent Connected Components Detection in Dynamic Graphs. Presentation of persistent connected components and a polynomial algorithm to detect the non-dominated ones in a dynamic graph and experimental results during AlgoTel 2020. This work was made with Yoann Pigné and Éric Sanlaville.

Visit AlgoTel 2020 page here.

See abstract of this presentation (in french) here.

September 2020, Lyon, France

ROADEF Conference 2020

Détection de composantes connexes persistantes non dominées dans un graphe dynamique

Non-dominated Persistent Connected Components Detection in Dynamic Graphs. Presentation of persistent connected components and a polynomial algorithm to detect the non-dominated ones in a dynamic graph and experimental results during the annual meeting of the French Operations Research and Decision Support Society. This work was made with Yoann Pigné and Éric Sanlaville.

Visit ROADEF 2020 page here.

February 2020, Montpellier, France

Journées Graphes et Algorithmes 2019

Composantes connexes persistantes dans les graphes dynamiques

Persistent connected components in dyamic graphs. Presentation of persistent connected components and an algorithm to compute them during the annual meeting of French working groups on graphs and algorithms. This work was made with Yoann Pigné and Éric Sanlaville.

Visit JGA 2019 page here.

See abstract of this presentation (in french) here and the presentation slides here.

November 2019, Brussels, Belgium

EURO Conference 2019

Persistent Connected Components on Temporal Networks

Presentation of persistent connected components, an extension of connected components in temporal networks, and an algorithm to retrieve them. This presentation was part of stream Algorithms on Graphs during the annual EURO conference. This work was made with Yoann Pigné and Éric Sanlaville.

Visit EURO 2019 page here.

See abstract of this presentation here.

June 2019, Dublin, Ireland

ROADEF Conference 2019

Un algorithme de plus courts chemins pour le problème de flot de coût minimum dans un graphe dynamique

Shortest paths algorithm for the minimum cost flow problem on dynamic graphs. Presentation of an SSP-inspired algorithm for minimum cost flow problem on dynamic graphs and experimental results during the annual meeting of the French Operations Research and Decision Support Society. This work was made with Maciej Drozdowski, Yoann Pigné and Éric Sanlaville.

Visit ROADEF 2019 page here.

See abstract of this presentation (in french) here.

February 2019, Le Havre, France

Cologne Twente Workshop 2018

Successive Shortest Path Algorithm for Flows in Dynamic Graphs

Presentation of an SSP-inspired algorithm for minimum cost flow problem on dynamic graphs during CTW18. This work was made with Maciej Drozdowski, Yoann Pigné and Éric Sanlaville.

Visit CTW18 page here.

See abstract of this presentation here.

June 2018, Paris, France

ROADEF Conference 2018

Algorithmique dans les graphes dynamiques : le cas des flots

Algorithms on dynamic graphs: focus on flow problems. Presentation of maximum flow problem on dynamic graphs during the annual meeting of the French Operations Research and Decision Support Society. This work was made with Yoann Pigné and Éric Sanlaville.

Visit ROADEF 2018 page here.

See abstract of this presentation (in french) here.

February 2018, Lorient, France

Invited Seminars

LIP6, Complex Networks

Modèles et algorithmes pour les graphes dynamiques

Models and algorithms for dynamic graphs. Presentation of my PhD thesis work with a focus on connectivity problems in a seminar for the Complex Networks team of the LIP6 Lab.

See the presentation slides here.

October 22 2020, Paris, France

Labri, AlgoDist and G&O

Dynamic graphs and connectivity

Presentation of connectivity problems in dynamic graphs in a seminar for the research groups Distributed Algorithms and Graphs and Optimisation in Combinatoire et Algorithmique team of the Labri Lab.

Connectivity in graphs is a well known issue, relevant to many applications. In the classical static context, it might seem simple even though some related problems are NP-complete. But in dynamic graphs, sometimes, even the simplest questions are far from trivial. What is the equivalent of a connected component in a dynamic graph ? How to identify those components ? In addition to connectivity itself, we can look at related problems. How to extend the definition of the Steiner problem in dynamic graphs ? This talk, based on my PhD thesis with Eric Sanlaville and Yoann Pigné, will consider those questions.

June 22 2020, Bordeaux, France (Online)

Institute of Computing Science, Poznan University of Technology

A Survey of Optimization Problems in Dynamic Graphs: A focus on Flow Problems

Presentation of dynamic graphs with a focus on flow problems in a lab seminar for the Institute of Computing Science, Poznan University of Technology.

November 21 2017, Poznan, Poland

Teaching

Algorithmics

Université Le Havre Normandie

Practical sessions for 2nd year bachelor students. Correction and complexity of algorithms, data structures. 24 hours.

Spring 2021

Java Programming

Université Le Havre Normandie

Practical sessions for 2nd year bachelor students. Polymorphism, exceptions, collections, lambda. 48 hours.

Spring 2021

Graph Theory

Université Le Havre Normandie

Theoretical lessons for 1st year master students in computer science and applied mathematics. Graph theory and graph algorithm. 20 hours.

Fall 2020

Graph Theory

Université Le Havre Normandie

Practical sessions for 1st year master students in computer science and applied mathematics. Graph algorithm, graph Java library. 20 hours.

Fall 2020

Computer skills

Université Le Havre Normandie

Practical sessions for 1st year bachelor students. Archive files, emails, word processing. 16 hours.

Fall 2020

Java Programming

Université Le Havre Normandie

Practical sessions for 2nd year bachelor students. Polymorphism, exceptions, collections, lambda. 48 hours.

Spring 2020

Graph Theory

Université Le Havre Normandie

Theoretical lessons and practical sessions for 1st year master students. Graph algorithm, graph Java library. 4 hours of theoretical lessons and 9 hours of practical lessons.

Fall 2019

Java Programming

Université Le Havre Normandie

Practical sessions for 2nd year bachelor students. Polymorphism, exceptions, collections, lambda. 48 hours.

Spring 2019

Computer skills

Université Le Havre Normandie

Practical sessions for 1st year bachelor students. Archive files, emails, word processing. 16 hours.

Fall 2018

Education

PhD Thesis in Computer Science

Normandie Université, Le Havre, France

Defended on October 19th, 2020 before the jury composed of Nadia Brauner, Arnaud Casteigts, Paul Dorbec, Christophe Picouleau, Yoann Pigné, Éric Sanlaville.

See manuscript (in French) here.

Models and algorithms for dynamic graphs. Graph problems have been widely studied in the case of static graphs. However, these graphs do not allow a time dimension to be considered, even though time is an important variable for the situations to model. Dynamic graphs make it possible to model evolution over time. This is a reason to wonder about graph problems in a dynamic context. First, it is necessary to define the most appropriate dynamic graphs model and the precise problem on those graphs. When the problem cannot be efficiently solved directly using known static graph methods, an algorithm specific to dynamic graphs must be designed and analyzed theoretically and practically.
With that approach, this thesis' objective is to study graph problems' extensions to dynamic graphs. This works deals with several graph problems in a dynamic context by focusing on algorithmic aspects and without considering application domains.
Flow problems in dynamic graphs are first studied and we propose a polynomial algorithm to optimally solve the minimum cost flow problem for one dynamic graph model. Connectivity problems are then studied. Persistent connected components, an extension of connected components to dynamic graphs, are a set of vertices remaining connected for consecutive time steps. Analogously to the maximality concept of connected components in static graphs, a dominance concept between persistent connected components is defined. A polynomial algorithm to identify all non dominated connected components in a dynamic graph is designed. Several extensions to the definition of persistent connected components are studied. Finally, we propose several possible extensions of the Steiner problem to dynamic graphs. We focus on a special case and show the NP-completeness of the problem.

2020

Master of Science in Operations Research, Combinatorics and Optimization

Université Grenoble Alpes, Grenoble, France
2017

Bachelor's degree in Computer Science and Applied Mathematics

Université Grenoble Alpes, Grenoble, France
2015

Other Activities

Laboratory Council

LITIS Lab, Université Le Havre Normandie, Université Rouen Normandie, INSA Rouen, France

Elected member of the lab council. One meeting per month.

Visit Lab web page here (in french).

January 2020 - ...

Doctoral School Council

École Doctorale MIIS, Normandie Université, France

Elected member of the doctoral school council. About three meetings a year.

Visit Doctoral School web page here (in french).

September 2018 - June 2020