Séminaire en ligne



Le but de ce séminaire est de permettre à la communauté du GT d'avoir accès à des exposés en ligne réguliers (par exemple pour les personnes plus isolées) mais aussi de se retrouver régulièrement afin d'échanger sur l'actualité du GT.



Prochain séminaire :



Lundi 27 mai 14h00 (durée 45 min + questions)
Chien-Chung Huang (ENS, Paris)
An FPTAS for Connectivity Interdiction.

Lien vers le séminaire

Abstract: In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes the knapsack problem as a special case, hence it is NP-hard. For this problem, Zenklusen designed a polynomial-time approximation scheme (PTAS), and for the special case of unit edge costs, exact algorithms. He posed the question of whether a fully polynomial-time approximation scheme (FPTAS) is possible for the general case. We give an affirmative answer. For the special case of unit edge costs, we also give faster exact and approximation algorithms.



Séminaires passés :



Mardi 30 avril matin 10h30 (durée 45 min + questions)
Arnaud Mary (LBBE, Lyon)
Subgraph enumeration problems.

Lien vers le séminaire

Abstract: Given a non planar graph G, how can one efficiently list all planar subgraphs of G ? This task falls into the category of enumeration problems, which have seen many developments in recent years. After an introduction to enumeration problems, we will focus on problems consisting of enumerating the maximal subgraphs of a graph G that satisfy a given hereditary property P. We will cover some classical techniques as well as the most recent results, along with the most significant open questions.

Vendredi 22 mars 10h30 (durée 45 min + questions, suivi d'une discussion sur le format des séminaires suivants)
Alexandre Vigny (LIMOS, Clermont-Ferrand)
Connectivity under vertex failure, logic and algorithm.

Lien vers le séminaire

Abstract: Connectivity under vertex failure is the problem of testing whether two vertices are still connected after the deletion of several given vertices. We will explain how to solve this problem very efficiently. Our method can solve many more problems, all being expressible in various logics. The well known first-order logic (FO) can express many algorithmic problems on graphs, but fails to express whether two vertices are connected. We will then discuss logics that can express such properties: separator logic and disjoint-path logic.

This talk will contain a mix of algorithmic, logic, and graph theory. I will cover joint work with Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Szymon Toruńczyk.



edit


Séminaire en ligne

Équipes

Prix de thèse Graphes "Charles Delorme"

Thèses / HDR soutenues

Projets

Manifestations

Formations Master

Conseils Candidature

Développements Logiciels

Administration Accès restreint

edit - logout