Tue 03 December 2019 -- Pierre Bergé (LRI, University of Paris Saclay)

summary: We study NP-hard problems dealing with graphs containing blockages.

We analyze cut problems via the parameterized complexity framework. The size p of the cut is the parameter. Given a set of sources {s_1,...,s_k} and a target t, we propose an algorithm deciding whether a cut of size at ...

Fri 17 November 2017 -- Pierre Bergé (GALAC, LRI)

Résumé : Le problème du voyageur canadien (PSPACE-complet), en anglais Canadian Traveller Problem (CTP), est un problème d'optimisation généralisant le problème du plus court chemin entre deux noeuds d'un graphe pondéré et non orienté. Un voyageur part d'un noeud s et son objectif est d'arriver à t ...