Approximating maximum integral multiflows on bounded genus graphs

DOI10.4230/LIPICS.ICALP.2021.80MaRDI QIDQ7241179zbMATH OpenFDO

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

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.80

zbMATH Keywords

approximation algorithmsbounded genus graphsmulti-commodity flows

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Almost polynomial hardness of node-disjoint paths in grids
• An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximate min-max relations for odd cycles in planar graphs
• Arcs intersecting at most once
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Correlation clustering and two-edge-connected augmentation for planar graphs
• Curves von 2-manifolds and isotopies
• Excluded minors, network decomposition, and multicommodity flow
• Flow-cut gaps for integer and fractional multiflows
• Graph minors. XIII: The disjoint paths problem
• Graphs on surfaces
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Integer plane multiflows with a mixed number of demands
• Map-colour theorem.
• Minimal multicut and maximal integer multiflow: a survey
• Multiflow Feasibility: An Annotated Tableau
• Network flows. Theory, algorithms, and applications.
• New hardness results for routing on disjoint paths
• On the complexity of the disjoint paths problem
• On the Computational Complexity of Combinatorial Problems
• On the hardness of approximating Multicut and Sparsest-Cut
• On the homotopy test on surfaces
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• Topological designs
• Transforming curves on surfaces redux

This page was built for publication: Approximating maximum integral multiflows on bounded genus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241179)