Articles by Pierre Bergé

PHD defense: A guide book for the traveller on graphs full of blockages

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

Le problème du voyageur canadien

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