Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Samedi 16 Juin 2018

Convex bi-partitions of bipartite graphs

par Martin Dario Safe (Laboratoire MIS (Université de Picardie Jules Verne), et Laboratoire Cristal (Université de Lille)Labri, Bordeaux)

A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr