Approximating maximum integral multiflows on bounded genus graphs
share
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.
READ FULL TEXT