Approximating maximum integral multiflows on bounded genus graphs

Chien-Chung Huang (1) , Mathieu Mari (1) , Claire Mathieu (2) , Jens Vygen (3)

1 DI-ENS - Département d'informatique - ENS Paris
2 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
3 Universität Bonn = University of Bonn

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances.

Domaines: Algorithme et structure de données [cs.DS]; Géométrie algorithmique [cs.CG]

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen. Approximating maximum integral multiflows on bounded genus graphs. 2021. ⟨hal-03099895⟩