JGA2023 : Journées Graphes et Algorithmes 2023

8:30 - 8:50 (20min)

Accueil

Accueil des participant·es

8:50 - 9:50 (1h)

Théorie structurelle

Amphitéâtre Marie Curie

chair : François Pirot

› Tough graphs and Hamiltonian degree conditions - Cléophée Robin, Greyc, Laboratoire de Sciences du numérique, Caen 08:50-09:10 (20min)

› Bornes de type Caro-Wei pour les forêts linéaires induites - Robin Petit, Département dÍnformatique [Bruxelles] 09:10-09:30 (20min)

› Plongement aléatoire d'arbres de degré borné - Clément Legrand-Duchesne, Laboratoire Bordelais de Recherche en Informatique 09:30-09:50 (20min)

9:50 - 10:10 (20min)

Pause café

Amphitéâtre Marie Curie

10:10 - 10:50 (40min)

Graphes géométriques

Amphitéâtre Marie Curie

chair : Frédéric Havet

› Couvrez vite ces cycles que je ne saurais voir. - Gaétan Berthe, Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier 10:10-10:30 (20min)

› Recognizing unit multiple intervals is hard - Virginia Ardévol Martínez, Laboratoire dánalyse et modélisation de systèmes pour láide à la décision 10:30-10:50 (20min)

10:50 - 11:00 (10min)

Pause café

Amphitéâtre Marie Curie

11:00 - 12:00 (1h)

Algorithmic aspects of finding large acyclic subgraphs of directed graphs

Amphitéâtre Marie Curie

Alantha Newman, chair : Frédéric Havet

12:00 - 14:00 (2h)

Déjeuner

Restaurant Domus

14:00 - 15:20 (1h20)

Graphes universels

Amphitéâtre Marie Curie

chair : Louis Esperet

› Graphes mineur-universels pour les graphes plongés sur des surfaces - Claire Hilaire, Famnit, University of Primorska 14:00-14:20 (20min)

› Construction de graphes universels via des réseaux de tri - Joseph Hyde, University of Victoria - Natasha Morrison, University of Victoria - Alp Müyesser, University College, London - Matias Pavez-Signé, University of Warwick 14:20-14:40 (20min)

› Graphes universels isométriques - Edgar Baucher, Laboratoire Bordelais de Recherche en Informatique 14:40-15:00 (20min)

› k-vertex-minor-universal graphs and small k-pairable quantum states - Nathan Claudet, Inria Mocqua, LORIA, CNRS, Université de Lorraine 15:00-15:20 (20min)

15:20 - 15:50 (30min)

Pause café

Amphitéâtre Marie Curie

15:50 - 16:50 (1h)

Algorithmique

Amphitéâtre Marie Curie

chair : Mathieu Liedloff

› Elementary first-order model checking for sparse graphs - Giannos Stamoulis, University of Warsaw 15:50-16:10 (20min)

› Complexité de l'énumération des séparateurs minimaux pour l'inclusion - Caroline Brosse, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes 16:10-16:30 (20min)

› Décroiser des graphes sur des surfaces - Loïc Dubois, LIGM 16:30-16:50 (20min)

16:50 - 17:00 (10min)

Pause café

Amphitéâtre Marie Curie

17:00 - 18:30 (1h30)

Business meeting

18:30 - 20:30 (2h)

Social Event

	Mar. 21	Mer. 22	Jeu. 23	Ven. 24
08:00 09:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00 18:00 19:00 20:00	Accueil 13:20 - 13:30 (10min) Accueil Accueil des participant·es https://jga2023.sciencesconf.org/data/program/Booklet_JGA.pdf Combinatoire extrémale et posets 13:30 - 14:30 (1h) Combinatoire extrémale et posets Amphitéâtre Marie Curie chair : Oscar Defrain › Extremal problems in locally sparse multigraphs - Victor Falgas-Ravry, Umeå University 13:30-13:50 (20min) › Saturation d'Antichaines Induites - Paul Bastide, LaBRI 13:50-14:10 (20min) › Le théorème de Dilworth dans les graphes temporels - Antoine Dailly, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes 14:10-14:30 (20min) Pause café 14:30 - 14:50 (20min) Pause café Amphitéâtre Marie Curie Algorithmique distribuée 14:50 - 15:50 (1h) Algorithmique distribuée Amphitéâtre Marie Curie chair : Alexandre Vigny › Certification locale de propriétés locales - Sébastien Zeitoun, Université Claude Bernard Lyon 1 14:50-15:10 (20min) › Trouver localement des petits ensembles dominants dans les graphes sans mineur K_2,t - Timothé Picavet, Laboratoire Bordelais de Recherche en Informatique 15:10-15:30 (20min) › Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks - Antoine El-Hayek, University of Vienna [Vienna] 15:30-15:50 (20min) Présentation des candidats à la co-direction du GT-Graphes 15:50 - 16:00 (10min) Présentation des candidats à la co-direction du GT-Graphes Amphitéâtre Marie Curie Pause café 16:00 - 16:30 (30min) Pause café Amphitéâtre Marie Curie Coloration 16:30 - 17:30 (1h) Coloration Amphitéâtre Marie Curie chair : Julien Bensmail › 1-extendable partition of graphs - Malory Marin, LIP 16:30-16:50 (20min) › Sous-arbres orientés dans les digraphes de grand nombre chromatique: chemins à blocs et arborescences - Amadeus Reinald, Algorithmes, Graphes et Combinatoire 16:50-17:10 (20min) › A note on interval colourings of graphs - Julien Portier, University of Cambridge 17:10-17:30 (20min)	Accueil 8:30 - 8:50 (20min) Accueil Accueil des participant·es Théorie structurelle 8:50 - 9:50 (1h) Théorie structurelle Amphitéâtre Marie Curie chair : François Pirot › Tough graphs and Hamiltonian degree conditions - Cléophée Robin, Greyc, Laboratoire de Sciences du numérique, Caen 08:50-09:10 (20min) › Bornes de type Caro-Wei pour les forêts linéaires induites - Robin Petit, Département dÍnformatique [Bruxelles] 09:10-09:30 (20min) › Plongement aléatoire d'arbres de degré borné - Clément Legrand-Duchesne, Laboratoire Bordelais de Recherche en Informatique 09:30-09:50 (20min) Pause café 9:50 - 10:10 (20min) Pause café Amphitéâtre Marie Curie Graphes géométriques 10:10 - 10:50 (40min) Graphes géométriques Amphitéâtre Marie Curie chair : Frédéric Havet › Couvrez vite ces cycles que je ne saurais voir. - Gaétan Berthe, Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier 10:10-10:30 (20min) › Recognizing unit multiple intervals is hard - Virginia Ardévol Martínez, Laboratoire dánalyse et modélisation de systèmes pour láide à la décision 10:30-10:50 (20min) Pause café 10:50 - 11:00 (10min) Pause café Amphitéâtre Marie Curie Algorithmic aspects of finding large acyclic subgraphs of directed graphs 11:00 - 12:00 (1h) Algorithmic aspects of finding large acyclic subgraphs of directed graphs Amphitéâtre Marie Curie Alantha Newman, chair : Frédéric Havet Déjeuner 12:00 - 14:00 (2h) Déjeuner Restaurant Domus Graphes universels 14:00 - 15:20 (1h20) Graphes universels Amphitéâtre Marie Curie chair : Louis Esperet › Graphes mineur-universels pour les graphes plongés sur des surfaces - Claire Hilaire, Famnit, University of Primorska 14:00-14:20 (20min) › Construction de graphes universels via des réseaux de tri - Joseph Hyde, University of Victoria - Natasha Morrison, University of Victoria - Alp Müyesser, University College, London - Matias Pavez-Signé, University of Warwick 14:20-14:40 (20min) › Graphes universels isométriques - Edgar Baucher, Laboratoire Bordelais de Recherche en Informatique 14:40-15:00 (20min) › k-vertex-minor-universal graphs and small k-pairable quantum states - Nathan Claudet, Inria Mocqua, LORIA, CNRS, Université de Lorraine 15:00-15:20 (20min) Pause café 15:20 - 15:50 (30min) Pause café Amphitéâtre Marie Curie Algorithmique 15:50 - 16:50 (1h) Algorithmique Amphitéâtre Marie Curie chair : Mathieu Liedloff › Elementary first-order model checking for sparse graphs - Giannos Stamoulis, University of Warsaw 15:50-16:10 (20min) › Complexité de l'énumération des séparateurs minimaux pour l'inclusion - Caroline Brosse, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes 16:10-16:30 (20min) › Décroiser des graphes sur des surfaces - Loïc Dubois, LIGM 16:30-16:50 (20min) Pause café 16:50 - 17:00 (10min) Pause café Amphitéâtre Marie Curie Business meeting 17:00 - 18:30 (1h30) Business meeting Business meeting Social Event 18:30 - 20:30 (2h) Social Event Social Event	Décompositions arborescentes 8:50 - 9:50 (1h) Décompositions arborescentes Amphitéâtre Marie Curie chair : Olivier Togni › A Structural Approach to Tree Decompositions of Knots and Spatial Graphs - Corentin Lunel, Laboratoire dÍnformatique Gaspard-Monge 08:50-09:10 (20min) › Diviser n'est pas régner ? - Laurent Lyaudet, indépendant 09:10-09:30 (20min) › Dynamic programming on bipartite tree decompositions - Laure Morelle, lirmm 09:30-09:50 (20min) Pause café 9:50 - 10:10 (20min) Pause café Amphitéâtre Marie Curie Grid minor 10:10 - 10:50 (40min) Grid minor Amphitéâtre Marie Curie chair : Daniel Gonçalves › Le théorème du mineur grille revisité - Clément Rambaud, Inria Université Côte d'Azur 10:10-10:30 (20min) › The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture - Ugo Giocanti, Laboratoire des sciences pour la conception, lóptimisation et la production 10:30-10:50 (20min) Pause café 10:50 - 11:00 (10min) Pause café Amphitéâtre Marie Curie A counting argument applied to graph colorings 11:00 - 12:00 (1h) A counting argument applied to graph colorings Amphitéâtre Marie Curie Matthieu Rosenfeld, chair : Daniel Gonçalves Déjeuner 12:00 - 14:00 (2h) Déjeuner Restaurant Domus Remise du prix Charles Delorme & Présentation des lauréat·es 14:00 - 15:00 (1h) Remise du prix Charles Delorme & Présentation des lauréat·es Amphitéâtre Marie Curie Pause café 15:00 - 15:15 (15min) Pause café Amphitéâtre Marie Curie Reconfiguration et jeux combinatoires 15:15 - 16:35 (1h20) Reconfiguration et jeux combinatoires Amphitéâtre Marie Curie chair : Aurélie Lagoutte › Reconfiguration of plane trees in convex geometric graphs - Lucas De Meyer, LIRIS 15:15-15:35 (20min) › Reconfiguration of homomorphisms - Thomas Suzan, Optimisation Combinatoire 15:35-15:55 (20min) › Reconfiguration par 2-adjacence dans la grille carrée - Florian Galliot, Laboratoire Bordelais de Recherche en Informatique 15:55-16:15 (20min) › Complexité du H-Game joué sur les arêtes d'un graphe. - Nacim Oijid, Laboratoire d'InfoRmatique en Image et Systèmes d'information 16:15-16:35 (20min) Pause café 16:35 - 16:50 (15min) Pause café Amphitéâtre Marie Curie Graphes orientés 16:50 - 18:10 (1h20) Graphes orientés Amphitéâtre Marie Curie chair : Pierre Aboulker › Diamètre-t coloration de graphes - Quentin Chuet, Laboratoire Interdisciplinaire des Sciences du Numérique 16:50-17:10 (20min) › Some problems and results on acyclic sets and colouring of digraphs - Gil Puig i Surroca, Laboratoire dánalyse et modélisation de systèmes pour láide à la décision 17:10-17:30 (20min) › Augmentation de l'hyperarc-connexité des hypergraphes orientés par réorientation d'hyperarcs - Benjamin Peyrille, Laboratoire des sciences pour la conception, lóptimisation et la production 17:30-17:50 (20min) › Complexité du problème de distance d'édition minimum à un line-digraphe - Quentin Japhet, Données et algorithmes pour une ville intelligente et durable - DAVID 17:50-18:10 (20min)	Algorithmique et séries génératrices 8:50 - 9:50 (1h) Algorithmique et séries génératrices Amphitéâtre Marie Curie chair : Thomas Bellitto › Asymptotiques pour les séries graphiquement divergentes - Khaydar Nurligareev, Laboratoire d'Informatique de Bourgogne [Dijon] 08:50-09:10 (20min) › Graphes d'activation dynamique - Antoine Castillon, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 09:10-09:30 (20min) › L'optimisation robuste pour les problèmes d'optimisation dans les graphes - Émile Naquin, Laboratoire Bordelais de Recherche en Informatique 09:30-09:50 (20min) Pause café 9:50 - 10:10 (20min) Pause café Amphitéâtre Marie Curie Ordres 10:10 - 10:50 (40min) Ordres Amphitéâtre Marie Curie chair : François Dross › Path eccentricity and the consecutive one property - Eileen Robinson, Département de mathématiques Université Libre de Bruxelles 10:10-10:30 (20min) › Détection de motifs dans les graphes ordonnés - François Pitois, Université Claude Bernard Lyon 1 - Faculté des sciences 10:30-10:50 (20min) Pause café 10:50 - 11:00 (10min) Pause café Amphitéâtre Marie Curie Problèmes d'identification dans les graphes 11:00 - 12:00 (1h) Problèmes d'identification dans les graphes Amphitéâtre Marie Curie Florent Foucaud, chair : François Dross Déjeuner 12:00 - 13:30 (1h30) Déjeuner Restaurant Domus Dimension métrique 13:30 - 14:30 (1h) Dimension métrique Amphitéâtre Marie Curie chair : Florent Foucaud › Bornes inférieures (double) exponentielles pour des problèmes dans NP paramétrés par treewidth & vertex cover - Fionn Mc Inerney, Vienna University of Technology 13:30-13:50 (20min) › Dimension métrique dans les graphes chordaux de largeur arborescente bornée - Quentin Deschamps, Laboratoire d'Informatique en Image et Systèmes d'information 13:50-14:10 (20min) › Ensemble géodésique de surveillance d'arcs - Pierre-Marie Marcille, Laboratoire Bordelais de Recherche en Informatique 14:10-14:30 (20min) Pause café 14:30 - 15:00 (30min) Pause café Amphitéâtre Marie Curie Algorithmique paramétrée 15:00 - 16:00 (1h) Algorithmique paramétrée Amphitéâtre Marie Curie chair : Julien Baste › Exact Algorithms and Lowerbounds for Multiagent Pathfinding - Foivos Fioravantes, Czech Technical University in Prague 15:00-15:20 (20min) › Calculer la Twin-Width: Algorithmes Paramétrés par le Feedback Edge Number - Mathis Rocton, Vienna University of Technology 15:20-15:40 (20min) › Complexité paramétrée de relaxations non-héréditaires de Clique - Ambroise Baril, Laboratoire Lorrain de Recherche en Informatique et ses Applications 15:40-16:00 (20min)