Approximating maximum integral multiflows on bounded genus graphs

DOI10.1007/s00454-023-00552-7arXiv2005.00575OpenAlexW3021855247MaRDI QIDQ6142346

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

Publication date: 21 December 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.00575

zbMATH Keywords

optimizationapproximation algorithmsmulticommodity flowbounded-genus graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Minimal multicut and maximal integer multiflow: a survey
• Approximate min-max relations for odd cycles in planar graphs
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• Integer plane multiflows with a mixed number of demands
• The four-colour theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• Flow-cut gaps for integer and fractional multiflows
• On loops intersecting at most once
• Arcs intersecting at most once
• On the complexity of the disjoint paths problem
• Topological designs
• On the hardness of approximating Multicut and Sparsest-Cut
• Curves von 2-manifolds and isotopies
• An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
• Multiflow Feasibility: An Annotated Tableau
• New Hardness Results for Routing on Disjoint Paths
• On Odd Cuts and Plane Multicommodity Flows
• On the Computational Complexity of Combinatorial Problems
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
• A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals
• Excluded minors, network decomposition, and multicommodity flow
• Transforming Curves on Surfaces Redux

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