Approximating maximum integral multiflows on bounded genus graphs

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen

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.

Knowledge Graph



Sign up or login to leave a comment