Séminaire
|
Date : 19 octobre 2023 14:00 - Salle :Amphi 3 - Pôle commun
Approximation, edge-disjoint paths, planar graphs and beyondClaire 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