Séminaire


Date : 19 octobre 2023 14:00 - Salle :Amphi 3 - Pôle commun

Approximation, edge-disjoint paths, planar graphs and beyond


Claire MATHIEU, DR CNRS - IRIF Paris

We discuss constant factor approximation algorithms for connect the maximum number of demand pairs (si,ti) with edge-dijoint paths in a “supply” graph, when the supply graph together with the graph of demands forms a planar graph, as well as generalizations to bounded genus graphs. The techniques use linear programming, topology, duality, and coloring, among others. This is based on joint work with Chien-Chung Huang, Mathieu Mari, Kevin Schewior and Jens Vygen.

https://fr.wikipedia.org/wiki/Claire_Mathieu